分为5个一组实现.cpp

来自「用分治法实现找K小元素」· C++ 代码 · 共 43 行

#include<stdio.h>

int  partition(int a[],int p,int r)
{

int i=p,j=r+1;
int x=a[p];
//将小于X的元素交换到左边区域
while(true)
{
while(a[++i]<x&&i<r);
while(a[--j]>x);
if(i>=j) break;

//作swap(a[i],a[j])
int temp=a[i];
a[i]=a[j];
a[j]=temp;

}


a[p]=a[j];
a[j]=x;
return j;


}


int select(int a[],int p,int r,int k)
{
if(r-p<75)//用某个简单排序算法对数组排序；
return a[p+k-1];

for(int i=0;i<=(r-p-4)/5;i++)
将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置；
int x=select(a,p,p+(r-p-4)/5,(r-p-4)/10);
int i=partition(a,p,r,x),j=i-p+1;
if(k<=j) return select(a,p,i,k);
else     return select(a,i+1,r,k-j);

}