实验二：线性时间选择

实验二：线性时间选择

1. 问题描述

（1）线性时间选择问题

给定线性序集中n个元素和一个整数k，1<=k<=n.要求找出这n个元素中第k小的元素，即如果将这个n个元素依其线性序排列时，排在第k个位置的元素就是要找的元素，当k==1时，要找的就是最小的元素；当k==n，就是最大的元素；当k=（n+1）/2，称为中位数。

1. 实验目的

（1）掌握线性时间选择算法

（2）体会线性时间选择算法中蕴含的分治思想

1. 实验原理

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

（3）线性时间选择

一个很简单的想法就是先排序后找，但这样算法的性能依赖于所选择排序算法的性能，比如快排就很快，冒泡就很慢。

我们可以模仿快速排序算法，对输入数组进行递归划分。与快速排序不同的是，它只对划分出的子数组之一进行递归处理。

一种改进的思路是：如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的两个子数组长度都至少为原数组长度的e倍（0<e<1是某个正常数），那么在最坏情况下用O(n)时间就可以完成选择任务。例如，若e=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间Tn满足递归式Tn<=T(9n/10)+O(n)。由此可得T(n)=O(n)

（1）将n个输入元素划分成n/5个组，每组5个元素，除可能有一个组不是5个元素外。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。

（2）递归调用Select找出这n/5个元素的中位数。如果n/5是偶数，就找它的两个中位数中较大的一个。然后以这个元素作为划分基准。

（所有的n/5都向上取整，取整号打不出来。。。）

1. 实验设计

4.1 线性时间选择

在前面快速排序的基础上进行线性时间选择。

首先是先排序后找target值。这种办法对于数组规模较小的情况有效。但对于大规模的数组，显然有更好的办法优化线性时间选择的算法。

整个c文件分为5个函数：

1. swap交换函数。C语言没有原生的swap交换函数，因此自己写了一个。

2. Partition分区函数。用于对给定数组进行分区。

3. random函数。用于生成一定范围内的随机数。利用c语言原生的rand函数生成随机数，srand函数配合time.h的time函数播种种子。

4. Quicksort函数。上个文件的。

5. Select函数。用于选择和排序。

这几个函数有一部分是从上个快速排序函数继承下来的。

1. 实验结果与分析

5.1 线性时间选择

首先，线性时间选择存在越界可能性，即选择的target值超过数组本身范围，会打印出内存中的随机数。（c语言）截图如下：

除去越界问题，对线性时间选择的性能测试如下：

选择target=4（随便想的），在10，100,1 000，10 000，100 000顺序数组查找的时间如下（忽略生成时间和打印时间）：

图表体现的不是那么明显，一方面是c语言没有直接测量时间的函数，只能依赖于编译器给出的时间，但这个时间并不是绝对精确的；另一方面，时间包含了生成随机数和打印的时间，虽然最终的结果应该随着x坐标是线性的，但体现不明显。

查阅资料得知，c语言有时间测量模块time_t。我决定用time_t改良时间测量的精确性。同时将数据改为线性数据。改进后重新实验：

这次的线性就体现得很明显了。

1. 结论

线性时间选择的优化来自快速排序对基准数的优化，从自选数（一般为第一位），到随机数，最后是中位数。

1. 程序源码

7.1线性时间选择

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<unistd.h>

// Swap the district
void Swap(int a,int b){
    int temp=a;
    a=b;
    b=temp;
}

int Partition(int nums[],int left,int right,int x){
    int i=left,j=right+1;
    //int x=nums[left];
    while (1)
    {
        while (nums[++i]<x&&i<right);
        while (nums[--j]>x);
        if(i>=j)
            break;
        Swap(nums[i],nums[j]);
    }
    nums[left]=nums[j];
    nums[j]=x;
    return j;
}

int random(int max,int min){
    int origin = rand();
    int random_num = origin%(max-min+1)+min;
    return random_num;
}

// int RandomizedPartition(int a[],int p,int r){
//     srand((unsigned int)time(NULL));
//     int i=random(p,r);
//     Swap(a[i],a[p]);
//     return Partition(a,p,r);
// }

int QuickSort(int nums[],int left,int right){
    //@param: nums[]: numbers
    //@param: left: the number of the [0]
    if(left<right){
        int i=left;
        int j=right;
        int temp_middle=nums[left];//standard number

        while (i<j)
        {
            //from right to left,find a number smaller than standard number
            while (i<j&&nums[j]>=temp_middle)
            {
                j--;
            }
            if(i<j)
            {
                nums[i]=nums[j];
                i++;
            }
            while (i<j&&nums[i]<temp_middle)
            {
                i++;
            }
            if(i<j)
            {
                nums[j]=nums[i];
                j--;
            }           
        }
        nums[i]=temp_middle;
        QuickSort(nums,left,i-1);
        QuickSort(nums,j+1,right);        
    }
}

int Select(int nums[],int left,int right,int target){
    //judge by 75
    if(right-left<75){
        QuickSort(nums,left,right);
        return nums[left+target-1];
    }
    //NOT 75
    for(int i=0;i<=(right-left-4)/5;i++){
        //right-left-4 是一个划分组号的公式。比如组内有34个元素，
        //i的值就是(33-0-4)/5=29/5=5
        //找中位数的中位数，r-p-4即上面所说的n-5
        int s=left+5*i,t=s+4;
        for(int j=0; j<3; j++) //冒泡排序，从后开始排，结果使得后三个数是排好顺序的（递增）
        {
            for(int n=s; n<t-j; n++)
            {
                if(nums[n]>nums[n+1])
                Swap(nums[n],nums[n-1]);
            }
        }
        Swap(nums[left+1],nums[s+2]);
    }

    int x=Select(nums,left,left+(right-left-4)/5,(right-left-4)/10);
    int i=Partition(nums,left,right,x),j=i-left+1;
    if(target<=j){
        // printf("target<=j,j=%d\n",j);
        // printf("##left=%d\n",left);
        // printf("##right=%d\n",right);
        return Select(nums,left,i,target);
    }
    else
    {
        // printf("target>j,j=%d\n",j);
        // printf("##left=%d\n",left);
        // printf("##right=%d\n",right);
        return Select(nums,i+1,right,target-j);
    }
    
}

int main(void){
    int target=4;

    //int nums[100]={3,1,7,6,5,9,8,2,0,4,13,11,17,16,15,19,18,12,10,14,23,21,27,26,25,29,28,22,20,24,33,31,37,36,35,39,38,32,30,34,43,41,47,46,45,49,48,42,40,44,53,51,57,56,55,59,58,52,50,54,63,61,67,66,65,69,68,62,60,64,73,71,77,76,75,79,78,72,70,74,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100};
    int max_num=100000;
    int nums[max_num];
    for(int i=0;i<max_num;i++){        
        nums[i]=i+1;        
        // printf("%2d,",nums[i]);
        // if(nums[i]%10==0) printf("\n");
    }

    //计时
    clock_t stime = clock();
    if(target>max_num||target<=0){
        printf("越界了！");
        printf("越界结果：第%d大的数是%d\n",target,Select(nums,0,max_num,target));
    }else
    {
        printf("第%d大的数是%d\n",target,Select(nums,0,max_num,target));
    }
    clock_t etime = clock();
    printf("time is %d ms",etime-stime);
    
    return 0;
}