【C++】快速排序(附详细注释) 选取序列内一随机元素作为主元

  快速排序的主要原理是选取序列内一元素存入变量当中，这个元素称为主元，将比此主元大的放到变量右边，将小于等于主元的元素放在主元左边，然后对以主元划分开的左右两个区间依次进行上述操作。

#include

using namespace std;
//选取一序列中元素，将比此元素大的元素移至此元素右边，将比此元素小的元素移至此元素左边,最后返回left和right相遇的下标 
int Partition(int A[], int left, int right){
	int temp = A[left];//选取A[left]存入临时变量
	while(left < right){//只要left和right不相遇 
		while(left < right && A[right] >temp) right--;//左移right 
		A[left] = A[right];//将大于temp的元素移至A[left] 
		while(left < right && A[left] <= temp) left++;//右移left 
		A[right] = A[left];//将小于temp的元素移至A[right] 
	} 
	A[left] = temp;//将一开始的主元放置在A[left]上 
	return left;
} 
//分别对以主元划分开的左右两区间进行快速排序 
void QuickSort(int A[], int left, int right){
	if(left < right){//left和right不相遇 
		int num = Partition(A, left, right);
		QuickSort(A, left, num-1);//对左区间进行归并排序 
		QuickSort(A, num+1, right);//对右区间进行归并排序 
	}
}

int main(){
	int a[10] = {6, 9, 7, 3, 2, 5, 6, 2, 8, 9};
	QuickSort(a, 0, 9);//归并排序 
	for(int i = 0; i < 10; i++) cout< 
  快速排序的平均时间复杂度为 O(n logn),值得注意的是,使用快速排序对序列进行排序时，序列中元素排列比较随机时效率最高，但是当序列中元素接近有序时，会达到最坏时间复杂度 O(n2) 。
   所以不能总是使用A[left]做主元，而是从序列中随机选取一个序列内元素作为主元，虽然这样做最坏时间复杂度仍然是 O(n2)，但是对任意输入数据的期望时间复杂度都能达到 O(n logn)。
 
生成随机数 
  首先来看一下如何生成随机数，生成随机数需要 stdlib.h 和 time.h 头文件，在 main 函数开头加上 srand((unsigned)time(NULL)); 语句生成随机数种子，如果想输出 [a,b] 范围内的随机数可使用 rand()%(b-a+1)+a 生成 [a,b] 内的随机数 。
 
#include
#include
#include

using namespace std; 
//生成十个[a,b]范围内的随机数
int main(){
	srand((unsigned)time(NULL));//生成随机数种子
	int a, b;
	cin>>a>>b; 
	for(int i = 1; i <= 10; i++){
		cout< 
随机选取主元的快速排序 
  知道了如何选取序列内随机元素作为主元，就可以实现随机选取主元的快速排序了。
 
#include
#include
#include

using namespace std;

//随机主元 快速排序
int randPartition(int A[], int left, int right){
	srand((unsigned)time(NULL));//生成随机数种子 
	int x = rand() % (right - left + 1) + left;//生成[left, right]内随机数 
	swap(A[x], A[left]);//交换A[x]和A[left]的值 
	//下面为非随机的快速排序划分过程 
	int temp = A[left];//选取A[left]存入临时变量
	while(left < right){//只要left和right不相遇 
		while(left < right && A[right] >temp) right--;//左移right 
		A[left] = A[right];//将大于temp的元素移至A[left] 
		while(left < right && A[left] <= temp) left++;//右移left 
		A[right] = A[left];//将小于temp的元素移至A[right] 
	} 
	A[left] = temp;//将一开始的主元放置在A[left]上 
	return left;
}
//分别对以主元划分开的左右两区间进行快速排序 
void QuickSort(int A[], int left, int right){
	if(left < right){//left和right不相遇 
		int num = randPartition(A, left, right);
		QuickSort(A, left, num-1);//对左区间进行归并排序 
		QuickSort(A, num+1, right);//对右区间进行归并排序 
	}
}

int main(){
	int a[10] = {6, 9, 7, 3, 2, 5, 6, 2, 8, 9};
	QuickSort(a, 0, 9);//归并排序 
	for(int i = 0; i < 10; i++) cout< 
附： 
算法笔记专栏持续更新中,期待各位关注。本文如有错误，欢迎各位在评论区指正。