✅作者简介：C/C++领域新星创作者，为C++和java奋斗中
✨个人社区：微凉秋意社区
🔥系列专栏：经典算法
📃推荐一款模拟面试、刷题神器👉注册免费刷题

🔥前言

今天还是算法的主题，分享快速排序的算法解析，并且使用vector容器实现，算是对知识的练习与巩固。这也是本专栏第七篇博文，以后遇到优化或者实用的算法我会继续写文分享在这一专栏，如果有朋友基础不牢或者初尝算法却不知道从何入手的都可以订阅观看《经典算法》专栏。

快速排序算法解析

一、掌握快排的算法流程

1. 算法思想如下：

通过一趟扫描将待排序的元素分割成独立的三个序列：第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置，因此需要再按此方法对第一个序列和第三个序列分别进行排序，整个排序过程可以递归进行，最终可使整个序列变成有序序列。

2. 其中的基准元素选择不唯一，可以采取以下五种方法：

• 取第一个元素
• 取最后一个元素
• 取位于中间位置的元素
• “三者取中的规则”
• 取位于low和high之间的随机数，用A[P]作为基准元素。即采用随机函数产生一个位于low和high之间的随机数P(low≤P≤high)，用A[P]作为基准，这相当于强迫R[low:high]中的元素是随机分布的

二、快排的代码实现与效果

C++源码：

#include
#include
#include
using namespace std;
//快排,分两步骤：分区和递归

//初始化动态数组
void getArray(vector<int>& v)
{
	srand((unsigned int)time(NULL));
	int n = 0;
	cout << "请出入数组的大小为："; cin >> n;
	for (int i = 0; i < n; i++) {
		v.push_back(rand() % 100 + 1);
	}
	cout << endl;
}
//使用迭代器打印数组元素
void printArray(vector<int>v) {
	for(vector<int>::iterator it=v.begin();it!=v.end();it++)
	{
		cout << *it << " " ;
	}
	cout << endl;
}
//快排第一步：分区
int divided(vector<int>&v,int low,int high)
{
	int p = v[low];
	while (low < high)
	{
		while (low < high && p <= v[high])
			high--;
		v[low] = v[high];
		while (low < high && p >= v[low])
			low++;
		v[high] = v[low];
	}
	v[low] = p;
	return low;
}
//快排第二部，递归
void repeact(vector<int>&v,int low,int high)
{
	if (low > high)	return;
	int flag = divided(v, low, high);
	repeact(v,low,flag-1);
	repeact(v,flag+1,high);

}
int main(void)
{
	vector<int>v;
	getArray(v);
	//sort(v.begin(),v.end());
	printArray(v);
	repeact(v, 0, v.size() - 1);
	printArray(v);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

运行效果：

---

三、具体代码分析

快速排序的代码相信网上有很多一样的，所以博主分享一个特别的：用动态数组vector容器实现快速排序。下面就是代码解析：

1、分区函数 divided

这里选择数组中左边界作为基准元素 p，外层while循环以及内层while循环的条件都要有low，这样做的目的是为了退出循环时让low和high相等。

对于内层while循环，由于我选的是左边界作为基准元素，那么我们就应该从数组右端往前依次与基准元素标记：如果基准元素小，右端元素向前移动，high递减；如果基准元素大，直接将右边小的元素扔到数组下标low的位置，不用担心左边界被覆盖，因为我们用基准元素记录了。然后用左端元素与基准元素比较，如果基准元素大，左端向右移动，low递增；如果基准元素小，将左端元素大的值扔到数组下标high的位置。直到low==high，循环结束，此时数组被分为两部分：low左边的值都要小于或者等于low右边的值。最后将基准元素赋到下标low的位置并返回该下标即可。

2、递归 repeact

• 使用递归来对数组的子序列进行划分，同样的子序列也会调用递归来对其子序列划分，直到子序列长度为零，这时候整个数组就是一个有序的序列了

首先给出递归结束的条件：low>high，这个条件什么时候会触发呢？上面以及提到了是子序列长度为零，所以我们每次调用递归 都要缩减序列的边界 。通过diveded函数来得到每次划分成两部分序列的下标，以此作为子序列的某一边界，这样随着程序的运行，子序列逐渐缩小，最终排序的结果就是我所想的。

3、初始化与打印函数

这里就是C++中vector容器的一些用法了：

• getArray函数里有srand作为随机数种子，利用push_back方法将产生的随机数循环插入到v容器中。
• printArray 函数使用迭代器来遍历输出容器中的数据，这些知识我也有写博客，可以在我的《C++提高》专栏里学习。

四、时间复杂度分析

• 最坏的情况

如果说待排序列已经有序，那么快速排序分区的时候需要一个一个的比较、移动，根本不会发生多个子序列的情况，与冒泡无差别，时间复杂度为：O($n^2$)

• 最好的情况

由于算法是不断在子序列上递归执行的，如果说每次待排元素都恰好处在中间位置，将原有序列分成两个等长的子序列，每次划分都是这样的情况，那么总共的划分次数就可以用O(log2n)表示，这样时间复杂度可以在O(n log2 n)。

• 平均情况

快速排序是基于关键字比较的内部排序算法中速度最快的，平均性能可达O($nlog2$ n)。

---

有关快速排序的算法解析到此结束了，期待你的关注和鼓励~