快速排序

概述

快速排序（Quick Sort）是从冒泡排序算法演变而来的，实际上是在冒泡排序基础上的递归分治法。快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

动画展示

我们借用五分钟学算法的gif动图来展示快速排序的过程

思路解析

1. 初始序列3 5 8 1 2 9 4 7 6

2. 这里第一步选择最后一个元素6为基准值

3. 初始左指针位置为第一个元素3，右指针位置为除基准外的最后一个值7

4. 左指针先走，左指针的职责就是往右走直到遇到大于基准值的元素

5. 右指针的职责就是往左走直到遇到小于基准值的元素

6. 当左右指针都停止并且还没相遇的时候就交换左指针所指元素和右指针所指元素

7. 如果左右指针相遇，说明相遇的位置就是基准值的位置，左边全是比基准值小的元素，右边全是比基准值大的元素，这里就体现了分支递归的思想。

8. 左右部分各重复上述过程

算法性能

时间复杂度

1. 最坏情况（Worst Case）
   • 当选择的枢轴（pivot）是数组中的最小或最大元素时，会导致数组极不平衡，一个子数组为空，另一个子数组包含所有剩余的元素。这种情况下，快速排序会退化为类似冒泡排序的性能。
   • 时间复杂度：O(n^2)，其中n是数组的大小。
2. 最好情况（Best Case）
   • 当选择的枢轴将数组完全均分为两个大小相等的子数组时，快速排序的性能最优。
   • 时间复杂度：O(n log n)，其中n是数组的大小。
3. 平均情况（Average Case）
   • 在随机选择枢轴或采用适当的枢轴选择策略（如三数取中法）时，快速排序的性能通常接近其最优情况。
   • 时间复杂度：O(n log n)，其中n是数组的大小。

空间复杂度

1. 原地排序（In-place Sorting）
   • 快速排序是一种原地排序算法，意味着它只需要一个常数级别的额外存储空间（用于递归调用栈和一些临时变量）。
   • 空间复杂度：O(log n)（由递归调用栈产生），其中n是数组的大小。在最坏情况下（例如，当数组已经接近有序，并且枢轴选择导致极不平衡的划分时），递归深度可能会达到n，但这种情况在平均和最好情况下很少发生。
2. 非原地实现
   • 如果实现中使用了额外的数组来存储子数组，则空间复杂度会增加。
   • 例如，如果每次划分后都将子数组复制到新的数组中，那么空间复杂度可能会增加到O(n)

稳定性

不稳定

代码实现

个人习惯基准值喜欢取中间值

#include <iostream>
#include <vector>

using namespace std;

//参数：数组，左边界，右边界(左闭右闭区间)
void quick_sort(vector<int>& v, int l, int r) {
	//结束条件
	if (l >= r) return;
	//中间值为基准
	int x = v[(l + r) >> 1];
	//初始化左右指针的位置
	int i = l - 1, j = r + 1;
	//左右指针未相遇就一直执行
	while (i < j) {
		do i++; while (v[i] < x);
		do j--; while (v[j] > x);
		if (i < j) swap(v[i], v[j]);
	}
	//递归调用左区间
	quick_sort(v, l, j);
	//递归调用右区间
	quick_sort(v, j+1, r);
}

int main() {
	vector<int> v = { 3,1,2,5,4 };
	quick_sort(v, 0, v.size() - 1);
	for (const auto value : v)
		cout << value << ' ';
	cout << endl;
	return 0;
}