线性时间选择—寻找第k小的数（分治算法）

问题描述：

找出一个数组中第K小的元素，时间复杂度为O(n)。

思想

首先，找出数组元素的中位数的中位数，然后利用Partition函数对整个数组进行划分，以数组中中位数的中位数为基准将数组划分为两部分——左边部分的所有数都小于基准，右边部分都大于基准，并返回基准数的下标值。

最后，如果要找到第k小个数,就将k的大小与数组左半边元素的个数（包括基准）进行比较，如果k小于j，则对左边部分进行递归，找第k小个数；若k大于j，则对右边部分进行递归，找第k减去j个小数。

代码如下：

#include "stdafx.h"#include <stdlib.h>#include<time.h>#define MAX 100void swap(int &a,int &b)//交换两个数的位置{int p;p=a;a=b;b=p;}void bubbleSort(int a[],int p,int r){//冒泡排序for(int i=p;i<r;i++){for(int j=i+1;j<=r;j++){if(a[j]<a[i]){swap(a[i],a[j]);}}}}int Partition(int a[],int p,int r,int val){//随机划分函数int pos;for(int q=p;q<=r;q++){if(a[q]==val){pos=q;//记录中位数的中位数的位置break;}}swap(a[p],a[pos]);//将中位数的中位数与第一个数交换位置int i=p,j=r;int tmp=a[i];while(i<j){//快速排序while(i<j&&a[i]>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;return i;//返回中位数的中位数排序后的位置}int select(int a[],int p,int r,int k){if(r-p<75){//当数据个数小于75时，算法select的计算时间不超过某一常数，直接调用冒泡排序算法即可bubbleSort(a,p,r);//冒泡排序return a[p+k-1];//返回第k小的数}//当数组个数个数大于75时，算法select的计算时间与数据个数线性相关for(int i=0;i<=(r-p-4)/5;i++){//把每个组的中位数交换到区间[p,p+(r-p-4)/4]int s=p+5*i,t=s+4; for(int j=0;j<3;j++){//冒泡排序，从后开始排，结果使得后三个数是排好顺序的for(int n=s;n<t-j;n++){if(a[n]>a[n+1]){swap(a[n],a[n-1]);}}}swap(a[p+1],a[s+2]);//交换每组中的中位数到前面}//(r-p-4)/5表示组数-1，则[p,p+(r-p-4)/5]的区间长度等于组数int x=select(a,p,p+(r-p-4)/5,(r-p-4)/10);//求中位数的中位数的值int c=Partition(a,p,r,x);//快速排序并返回中位数的位置intj=c-p+1;//求中位数之前包括中位数的元素个数if(k<=j){//如果k小于中位数之前的元素的个数，对之前的元素递归调用select方法return select(a,p,c,k);}else {//如果k大于中位数之前的元素的个数，对之后的元素递归调用select方法return select(a,c+1,r,k-j);}}int main(int argc, char* argv[]){printf("数据个数小于75时：\n");printf("输入数据(输入00结束)：\n");int b[MAX];int i=0;int c;while(scanf("%d",&c)&&c!=00)b[i++]=c;printf("输入k的值：\n");int k;scanf("%d",&k);int d=select(b,0,i-1,k);printf("第%d小的元素为：%d \n",k,d);printf("\n");printf("数据个数大于75时：\n");int a[MAX];srand(time(NULL));//利用时间设置种子，使每次产生的随机数不一样for(int j=0;j<100;j++){a[j]=rand()%100;//产生100个随机数}for(int l=0;l<100;l++){printf("%d ",a[l]);//打印随机数}printf("\n");printf("输入k的值：\n");int y;scanf("%d",&y);int x=select(a,0,99,y);printf("第%d小的元素为：%d \n",y,x);printf("排序后的结果为：\n");for(int w=0;w<100;w++){bubbleSort(a,0, 99);printf("%d ",a[w]);}return 0;}

运行结果：