一、题目
假定元素的值不同,说明如何才能使快速排序在最坏情况下以O(nlgn)时间运行
二、思考
要改善最坏情况的下运行时间,就要从划分入手,保证即使是最坏情况,也要尽量均衡地划分。
因此,使用SELECT找到中值,再以这个中值为主元进行划分
三、代码
1.以RANDOMIZED-SELECT作为选择中值的算法
//9.3-3 #include <iostream> using namespace std; //已经出现很多次了,不解释 int Partition(int *A, int p, int r) { int x = A[r], i = p-1, j; for(j = p; j < r; j++) { if(A[j] <= x) { i++; swap(A[i], A[j]); } } swap(A[i+1], A[r]); return i+1; } //以f为主元的划分 int Partition2(int *A, int p, int r, int f) { int i; //找到f的位置并让它与A[r]交换 for(i = p; i < r; i++) { if(A[i] == f) { swap(A[i], A[r]); break; } } return Partition(A, p, r); } int Randomized_Partition(int *A, int p, int r) { //随机选择数组中一个数作为主元 int i = rand() % (r-p+1) + p; swap(A[r], A[i]); //划分 return Partition(A, p, r); } //i是从1开会计数的,不是从p开始 int Randomized_Select(int *A, int p, int r, int i) { if(p == r) return A[p]; //以某个元素为主元,把数组分为两组,A[p..q] <= 主元 < A[q+1..r],返回主元在整个数组中的位置 int q = Randomized_Partition(A, p, r); //主元是整个数组中的第q个元素,是A[p..r]数组中的第k个元素 int k = q - p + 1; if(i == k) return A[q]; else if(i < k)//所求元素<=主元,则在A[p..q-1]中继续寻找 return Randomized_Select(A, p, q-1, i); else//所求元素>主元,则在A[q+1..r]中继续寻找 return Randomized_Select(A, q+1, r, i-k); } void QuickSort(int *A, int p, int r) { if(p >= r) return ; //用RANDOMIZED-SELECT作为选择中值的算法选择中值 int i = (r - p + 1) / 2; int x = Randomized_Select(A, p, r, i); //以这个中值为主元进行划分 // int q = Partition2(A, p, r, x); //分别对划分后的前后两个部分进行排序 QuickSort(A, p, p+i-2); QuickSort(A, p+i, r); } int main() { int length_A, i; cin>>length_A; //生成随机数据 int *A = new int[length_A+1]; for(i = 1; i <= length_A; i++) A[i] = rand() % 100; for(i = 1; i <= length_A; i++) cout<<A[i]<<' '; cout<<endl; //排序 QuickSort(A, 1, length_A); //输出结果 for(i = 1; i <= length_A; i++) cout<<A[i]<<' '; cout<<endl; delete []A; return 0; }
运行结果:
2.以最坏情况下线性时间作为选择中值的算法
//9.3-3使用最坏情况线性时间算法作为选择中值算法 #include <iostream> using namespace std; //已经出现很多次了,不解释 int Partition(int *A, int p, int r) { int x = A[r], i = p-1, j; for(j = p; j < r; j++) { if(A[j] <= x) { i++; swap(A[i], A[j]); } } swap(A[i+1], A[r]); return i+1; } int Select(int *A, int p, int r, int i); //对每一组从start到end进行插入排序,并返回中值 //插入排序很简单,不解释 int Insert(int *A, int start, int end, int k) { int i, j; for(i = 2; i <= end; i++) { int t = A[i]; for(j = i; j >= start; j--) { if(j == start) A[j] = t; else if(A[j-1] > t) A[j] = A[j-1]; else { A[j] = t; break; } } } return A[start+k-1]; } //根据文中的算法,找到中值的中值 int Find(int *A, int p, int r) { int i, j = 0; int start, end, len = r - p + 1; int *B = new int[len/5+1]; //每5个元素一组,长度为start到end,对每一组进行插入排序,并返回中值 for(i = 1; i <= len; i++) { if(i % 5 == 1) start = i+p-1; if(i % 5 == 0 || i == len) { j++; end = i+p-1; //对每一组从start到end进行插入排序,并返回中值,如果是最后一组,组中元素个数可能少于5 int ret = Insert(A, start, end, (end-start)/2+1); //把每一组的中值挑出来形成一个新的数组 B[j] = ret; } } //对这个数组以递归调用Select()的方式寻找中值 int ret = Select(B, 1, j, (j+1)/2); //delete []B; return ret; } //以f为主元的划分 int Partition2(int *A, int p, int r, int f) { int i; //找到f的位置并让它与A[r]交换 for(i = p; i < r; i++) { if(A[i] == f) { swap(A[i], A[r]); break; } } return Partition(A, p, r); } //寻找数组A[p..r]中的第i大的元素,i是从1开始计数,不是从p开始 int Select(int *A, int p, int r, int i) { //如果数组中只有一个元素,则直接返回 if(p == r) return A[p]; //根据文中的算法,找到中值的中值 int f = Find(A, p, r); //以这个中值为主元的划分,返回中值在整个数组A[1..len]的位置 //因为主元是数组中的某个元素,划分好是这样的,A[p..q-1] <= f < A[q+1..r] int q = Partition2(A, p, r, f); //转换为中值在在数组A[p..r]中的位置 int k = q - p + 1; //与所寻找的元素相比较 if(i == k) return A[q]; else if(i < k) return Select(A, p, q-1, i); else //如果主元是数组中的某个元素,后面一半要这样写 return Select(A, q+1, r, i-k); //但是如果主元不是数组中的个某个元素,后面一半要改成Select(A, q, r, i-k+1) } void QuickSort(int *A, int p, int r) { if(p >= r) return ; //用RANDOMIZED-SELECT作为选择中值的算法选择中值 int i = (r - p + 1) / 2; int x = Select(A, p, r, i); //以这个中值为主元进行划分 int q = Partition2(A, p, r, x); //分别对划分后的前后两个部分进行排序 QuickSort(A, p, q-1); QuickSort(A, q+1, r); } int main() { int length_A, i; cin>>length_A; //生成随机数据 int *A = new int[length_A+1]; for(i = 1; i <= length_A; i++) A[i] = rand() % 100; for(i = 1; i <= length_A; i++) cout<<A[i]<<' '; cout<<endl; //排序 QuickSort(A, 1, length_A); //输出结果 for(i = 1; i <= length_A; i++) cout<<A[i]<<' '; cout<<endl; delete []A; return 0; }