序言
刚开始我认为，寻找第k小的元素：简单呀，先对所有元素排序，之后再找不就完事啦，这时时间复杂度在O(nlgn)。那有没有更好的排序的方法了呢？答案：当然是有的。
算法基本思路：
(1) 当规模小于某一阈值时，直接用排序算法返回结果。
(2) 当n大于阈值时，把n个元素划分为|_ n/5> _|，若n不是5的倍数，则排除剩余元素（不会有影响，这里只是为了求中项mm），分别排序，然后挑出每一组元素的中间值，再在所有的中间值中，递归调用本算法，挑出中间值mm，mm即为中项的中项。
(3) 将所有元素划分为A1、A2、A3三组，分别包含小于、等于、大于mm的元素。
(4)分三种情况，求出第k小元素在这三个数组中的哪一个：
a.若A1的元素数量大于等于K，即第K个元素在第一组内：在A1中递归查找第k小元素。
b.若A1、A2元素个数之和大于等于K，即中项mm为第K个元素：返回mm
c.否则，第K个元素在第三组：在A3中递归寻找第（k-|A1、A2元素数量之和|）小元素。
伪代码
code(已验证)
归并排序：
#include <stdio.h>#include <stdlib.h>#include <math.h>#define N 100//归并排序void Mergesort(int *A,int low,int high,int *temp){if(low < high){int mid = (high+low)/2;Mergesort(A,low,mid,temp);Mergesort(A,mid+1,high,temp);MERGE(A,low,mid,high,temp);}}void MERGE(int *A,int low,int mid,int high,int *temp){int i=low;int j=mid;int m=mid+1;int n=high;int k=0;//开始合并两个数组；while(i <= j && m <= n){if(A[i] <= A[m]){temp[k++] = A[i++];}else{temp[k++] = A[m++];}}while(i <= j){temp[k++] = A[i++];}while(m <= n){temp[k++] = A[m++];}//把temp数组中的结果装回A数组for(i = 0; i < k; i++){A[i+low] = temp[i];}}
寻找第k小元素：
//寻找第k小元素int select_k(int *a,int low,int high,int k){int p,q,i,mm; //mm为中项集合的中项int *M = (int *)malloc(N*sizeof(int));int *temp = (int *)malloc(N*sizeof(int)); //辅助数组p = high-low +1; //元素总个数if(p<6) //若p小于阈值44直接排序得到第k小元素{Mergesort(a,low,high,temp);return a[k];}q = p/5; //将所有元素分成的总组数for(i=1;i<=q;i++){Mergesort(a,low+5*(i-1),low+5*(i-1)+4,temp);M[i] = a[low+5*(i-1)+2];}if(q==1){mm = M[1];}elsemm = select_k(M,1,q,q/2);int count1=1,count2=1,count3=1;int *A1 = (int *)malloc(N*sizeof(int));int *A2 = (int *)malloc(N*sizeof(int));int *A3 = (int *)malloc(N*sizeof(int));for(i=low;i<=high;i++){if(a[i] < mm){A1[count1++] = a[i];}else if(a[i] == mm){A2[count2++] = a[i];}else{A3[count3++] = a[i];}}if(count1-1 >= k){return select_k(A1,1,count1-1,k);}else if(count1-1 + count2-1 >= k){return mm;}else if (count1-1 + count2-1 <k){return select_k(A3,1,count3-1,k-(count1-1)-(count2-1));}elsereturn 0;}
主函数:
int main(){int i,a,n;//int num[25] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24};int *num = (int *)malloc(N*sizeof(int));FILE* fp = fopen("2.txt","r");//读文件if(fp==NULL){printf("没找到文件");return 0;}for(i=1;i<12;i++){fscanf(fp,"%d",&num[i]);}fclose(fp);printf("请输入需要查询第k项的数：eg：1，2，3~~");scanf("%d",&n);a = select_k(num,1,11,n);printf("第%d小数为：",n);printf("%d",a);return 0;}
注意：在寻找第k小元素代码中，一定要对q=1进行判断，mm=M[1].
