算法导论之最坏情况下为O(n)的选择算法

当n比较小时,隐含的常数较大

#include<iostream> #include<algorithm> using namespace std; int PARTITION(int a[], int l ,int r,int k)//k为分界值下标 { swap(a[r],a[k]); //把分界值交换到右边 int left = l,right = r,pivot = a[r]; while(left<right) { swap(a[left],a[right]); while(right>left&&a[right]>pivot)right--; while(left<right&&a[left]<=pivot)left++; } swap(a[right],a[l]); return left; } void insertsort (int a[],int l, int r)//插入排序非递归 { int key,i; for(int j=l+1;j<=r;j++) { key=a[j]; for(i=j-1;i>=l&&a[i]>key;i--) { a[i+1]=a[i]; } a[i+1]=key; } } int findmid(int a[],int l, int r) { if(r-l+1 <= 5){ insertsort(a,l,r); return (l+r)/2; } //当元素小于等于5 排序并返回分界值下标 int k=l,mid; int y = (r-l+1)%5; for(int i = l;i+4<=r;i+=5) { insertsort(a,i,i+4); swap(a[k],a[i+2]); k++; } if(y){ insertsort(a,r-y+1,r); swap(a[k],a[r-y/2]); k++; } return findmid(a,l,l+k-1); } int select(int a[],int l,int r,int i) { int pivot = findmid(a,l,r);//存储分界值的下标 int m = PARTITION(a,l,r,pivot); int k = m-l+1; if(i == k){ return a[m]; }else if(k>i){ return select(a,l,m-1,i); }else return select(a,m+1,r,i-k); } int main() { int a[11] = {11,233,13,3,3,22,65464,-1,-43,21221,4}; for(int i = 1;i<=11;i++) PRintf("%d ",select(a,0,10,i)); printf("\n"); insertsort(a,0,10); for(int i = 0;i<11;i++) printf("%d ",a[i]); }