算法中最小K元素的选择问题

/* 编程实现算法2.17：基于二次取中的选择算法编制一下过程： - PATITION - INSERTIONSORT - INTERCHANGE - SELECT2 每组大小为 7 ,该算法支持多个数相同的情况 */ #include <IOSTREAM> #include <CTIME> using namespace std; /*交换各分组的中位数到数组的前面部分去*/ template<class Type> void InterChange(Type &x,Type &y) { Type temp; temp = x; x = y; y = temp; } /*以数组的中位数的中位数为划分基准，对数组a[p,r]进行划分，返回划分元素所在的位置*/ template<class Type> int Partition(Type a[],int p,int r,Type x) { int i = p-1; int j = r + 1; while (true) { while (a[++i] < x && i < r); while (a[--j] > x); if (i >= j) break; InterChange(a[i],a[j]); } return j; } /*插入排序，当划分后的子数组小于一定规模时，对其进行排序，直接求第k小元素*/ template <class Type> void InsertSort(Type a[],int p,int r) { int i,j,temp; for (i = p+1;i <= r;i++) if (a[i] < a[i-1]) { temp = a[i]; for (j = i - 1; temp < a[j];--j ) { a[j+1] = a[j]; } a[j+1] = temp; } } template <class Type> int CountX(Type a[],int p,int r,Type x) { int count = 0; for (int i = p; i<= r;i++) { if (x == a[i]) count++; } return count-1;//返回与中位数的中位数相等的元素个数，但不包含x } template<class Type> Type Select(Type a[],int p,int r,int k) { if ((r-p)<70) { /*用插入排序算法对数组a[p:r]排序*/ InsertSort(a,p,r); return a[p+k-1];//返回数组a[p,r]的第k小元素 }; for (int i = 0;i <= (r-p-6)/7;i++) { /*将a[p+7*i]至a[p+7*i+4]]的第3小元素与a[p+i]交换*/ InsertSort(a,p+7*i,p+7*i+6); InterChange(a[p+7*i +3],a[p+i]); }; /*找中位数的中位数,r-p-6即上面所说的n-7*/ Type x = Select(a,p,p+(r-p-6)/7,(r-p-6)/14); i = Partition(a,p,r,x); int j = i-p+1;//i为中位数的中位数在数组的位置 /*求出与中位数的中位数相等的元素个数*/ int m = CountX(a,p,r,a[i]); if (k <= j) return Select(a,p,i,k);//k在划分元素的左半部分 else if((m >= 1) && (k >=j ) && (k <= j + m))//k是与划分元素相等的元素中的一个 return a[i]; else //return Select(a,i+m+1,r,k-j-m);//k在除去划分元素及其相等元素后数组的右半部分 return Select(a,i+1,r,k-j); } inline int Random(int x,int y) { int ran_num = rand() % (y-x) + x; return ran_num; } int main(int argc,char *argv[]) { const int SIZE = 100; int *a= new int[SIZE]; int p = 0,r = SIZE -1; srand((unsigned)time(0));//设置随机数的种子 cout << "打印出数组中所有的数据，每10个为一行：\n"; for (int i = 0;i < SIZE;i++) { a[i] = Random(0,500) ;//随机生成数组a[p:r]中的元素值(0~500之间) cout <<"a[" << i <<"] = " << a[i] << ' '; if ((i+1)%10 == 0) { cout << endl; } } int k; cout << "请输入你想查询的第k小元素，k = "; cin >>k ; cout << "第" << k <<"小元素为： "<< Select(a,p,r,k) << endl; cout << "数组元素值为： \n"; InsertSort(a,p,r); for (i = 0; i < 100;i++) { cout << "a[" << i << "] = " << a[i] << ' '; if ((i+1)%10 == 0) { cout << endl; } } cout << endl; delete[] a; return 0; }