Select

算法输入：$n$个元素的数组$A[1…n]$和正整数$k$，$1<=k<=n$。

算法输出：$A$中的第$k$小元素。

算法思想：现将数据按照每组5个大小分组，然后求出每一组的均值组成一个新的数组，求出新的数组mid_mid，根据mid_mid的值将数据分成3个大小的数组，将新分成的数组的大小和k比较，然后可以排除掉一部分数据，当这部分的数据比44小的时候，直接排序输出，否则的话继续运行上述步骤!

语法事项：

• 对于静态变量，下次递归调用的时候值会不变，不会重新重新赋值初始化

• 声明数组大小的时候，对于变量都不能直接A[n],即使这个值是从键盘中读出的，或者经过运算出来的。只能宏定义n的值。

• 声明数组大小的时候，可以动态分配大小。

• 可以A[] = { 数字}，不必指明大小。

• C语言中求不小于q/2的最小数可以用mid[(q+1)/2]

• C语言中求不大于q/2的最大数可以用mid[q/2]

• C语言中动态分配的数组指针要释放，当要递归调用的函数中包含数组指针的时候注意写法。

算法注意事项：s

• 对于不能被5整除的数，只是求中值的时候抛弃了，但是在下面根据中值重新分到3个数组的时候是没被抛弃的。
• 注意递归调用求中值的时候，传入的不是下标，而是第几个小的数。

算法代码：

#include<stdio.h>
#include<malloc.h>
void insertionsort(int *a, int N);
int SelectAlg(int *A, int low, int high, int k);

int main()
{
    int N,k,i;
    int *A;
    A = (int*)malloc(N * sizeof(int));
    printf("Please input the number of the array:");
    scanf("%d", &N);
    printf("Please input the list_number to find:");
    scanf("%d", &k);
    printf("Please input the array:");
    for(i=0; i<N; i++)
        scanf("%d",&A[i]);
    int k_num = SelectAlg(A, 0 , N-1 ,k);
    printf("%d", k_num);
    return 0;

}

int SelectAlg(int *A, int low, int high, int k)
{
    int p = high - low + 1;
    if (p < 44)
    {
        insertionsort(A, p);
        return A[k-1];
    }

    int i,j;
    int **L;
    int q = p/5;
    L = (int **)malloc(q * sizeof(int*));
    int *mid = (int *)malloc(q * sizeof(int));
    int *A_one = (int *)malloc(p * sizeof(int));
    int *A_two = (int *)malloc(p * sizeof(int));
    int *A_three = (int *)malloc(p * sizeof(int));
    int one = 0,two = 0,three = 0;

    //分配给q个大小的数组，每一个是5个大小,并找到每一个的中值，赋值给mid[]数组
    for (i = 0; i < q; ++i)
    {
        L[i] = (int *)malloc(5 * sizeof(int));
        for (j = 0; j < 5; ++j)
            L[i][j] = A[(5*i)+j];

        insertionsort(L[i], 5);
        mid[i] = L[i][2];
    }
    for (i = 0; i < q; ++i)
        free(L[i]);
    free(L);

    int mid_mid = SelectAlg(mid, 0, q-1, (q+1)/2);
    //insertionsort(mid, q);
    //int mid_mid = mid[(q+1)/2];

    //根据mid_mid 的大小，将A分成3组数据
    for (i = 0; i < p; ++i)
    {
        if(A[i] < mid_mid)
            A_one[one++] = A[i];

        else if(A[i] == mid_mid)
            A_two[two++] = A[i];

        else if(A[i] > mid_mid)
            A_three[three++] = A[i];
    }


    if (one >= k)
        mid_mid = SelectAlg(A_one, 0, one-1, k);
    else if((one + two) < k)
        mid_mid = SelectAlg(A_three, 0, three-1, k-one-two);

    free(mid);
    free(A_one);
    free(A_two);
    free(A_three);

    return mid_mid;
}

void insertionsort(int *a, int N){
     int i = 1;
     int j,x;
     while (i<N){
        int j = i;
        x = a[i];
        while ((j>0)&&(a[j-1]>x)){
               a[j] = a[j-1];
               j = j -1;
            }
        a[j] = x;
        i = i+1;
     }
}