问题描述：无序找第k小的数？

1、解法一

先排好序，再找第k小个数；返回A[k-1]；此解法的时间复杂度为：O(nlogn)；


2、解法二

情况一：k = 1 和 k = n 就是找数组的最小值和最大值；

情况二：找出中位数


3、找中位数(随机选择算法)

利用快速排序的原理，一轮排序，有2种情况：

if i = k-1；返回a[i]；

if i != k-1；左边/右边递归查找，时间复杂度为：O(n)；

具体思想：

分析：在大多数情况下的时间复杂度是：O(n)；但是最坏情况，完全顺序下找第k = n-1大数，此时的时间复杂度是：O(n^2)；


4、无序找第k小值

快排的升序实现思想，在加上递归查找；

(1)、代码实现

#include<stdio.h>voidfindKSmall(int*a,intstart,intend,intkey);voidfindKSmall(int*a,intstart,intend,intkey){inti=start;intj=end;inttmp=a[i];//快排中的升序while(i<j){while(i<j&&a[j]>tmp){j--;}if(i<j){a[i++]=a[j];}while(i<j&&a[i]<tmp){i++;}if(i<j){a[j--]=a[i];}}a[i]=tmp;if(key-1<i){findKSmall(a,0,i-1,key);}elseif(key-1>i){findKSmall(a,i+1,end,key);}else{return;}}voidmain(void){inta[]={8,4,6,9,2,3,7,9,11,10};intcount=sizeof(a)/sizeof(int);intk;inti;printf("请输入要查找的第k小的数：");scanf("%d",&k);findKSmall(a,0,count-1,k);for(i=0;i<count;i++){printf("%d",a[i]);}printf("\n%d\n",a[k-1]);}

结果截图


5、无序找第k大值

快排的降序实现思想，在加上递归查找；

(1)、代码实现

#include<stdio.h>voidfindKBigger(int*a,intstart,intend,intkey);voidfindKBigger(int*a,intstart,intend,intkey){inti=start;intj=end;inttmp=a[i];//快排中的降序while(i<j){while(i<j&&a[j]<tmp){j--;}if(i<j){a[i++]=a[j];}while(i<j&&a[i]>tmp){i++;}if(i<j){a[j--]=a[i];}}a[i]=tmp;if(key-1<i){findKBigger(a,0,i-1,key);}elseif(key-1>i){findKBigger(a,i+1,end,key);}else{return;}}voidmain(void){inta[]={8,4,6,9,2,3,7,9,11,10};intcount=sizeof(a)/sizeof(int);intk;inti;printf("请输入要查找的第k大的数：");scanf("%d",&k);findKBigger(a,0,count-1,k);for(i=0;i<count;i++){printf("%d",a[i]);}printf("\n%d\n",a[k-1]);}

(2)、结果截图



6、线性算法

(1)、划分为5个一组的元素，在找出每一组的中值(对这5个数进行排序，找出中值)，时间复杂度：O(n)

(2)、用递归去找这些中值中的那一个中值(中值中的中值)；

(3)、此时用这个最中值的下标和k作比较，之后和上面的随机选择算法一样！！！

具体模型如下：


算法分析

找中值和第k小数时间复杂度均为：O(n)；比较好的解决了上述最坏时间复杂度为O(n^2)的情况；

3个元素一组的话，结果不成立；

5是这个算法能成功的最小数字，7个元素为一组算法也能成立，但是性能不会有所提高；