快速排序

算法思想

快速排序的基本思想：

  1. 双指针向中间移动

    • 通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数
    • 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

  2. 双指针向右移动

    • 找第一个或者最后一个值，在数组中遍历一遍，找到其应该在的位置，将它放在位置上然后在递归操作其前后的子数组找到其应该在的位置
    • 要有两个指针一个i指向最前面，一个j往后移动，当j指向的数组的值比最后一个元素小则和在最前面的指针i的值交换，最后当j遍历完后再将i和最后一个值进行交换
    • 操作完基准值后，基准值前面的值都比基准值小，基准值后面的值都比基准值大 (不要求又大又有序）

==这两种方法都要将剩余数据遍历一遍，所以复杂度什么的都一样，只是两个不同的理解思路而已==

时空间复杂度

时间复杂度

当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。$O(n^2)$
而当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。 $O(nlogn)$
平均时间复杂度为 $O(nlogn)$
总之，数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差

空间复杂度

快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 $\log N$ 次的分割处理，所以占用空间也是 $\log N$ 个。

稳定性

在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法

源代码

双指针向中间移动（图示方法）

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
#include <iostream>
#include <vector>

using namespace std;

int division(vector<int> &list, int left, int right){
	// 以最左边的数(left)为基准
	int base = list[left];
	while (left < right) {
		// 从序列右端开始，向左遍历，直到找到小于base的数
		while (left < right && list[right] >= base)
			right--;
		// 找到了比base小的元素，将这个元素放到最左边的位置
		list[left] = list[right];

		// 从序列左端开始，向右遍历，直到找到大于base的数
		while (left < right && list[left] <= base)
			left++;
		// 找到了比base大的元素，将这个元素放到最右边的位置
		list[right] = list[left];
	}

	// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
	// 而left位置的右侧数值应该都比left大。
	list[left] = base;
	return left;
}

// 快速排序
void QuickSort(vector<int> &list, int left, int right){
	// 左下标一定小于右下标，否则就越界了
	if (left < right) {
		// 对数组进行分割，取出下次分割的基准标号
		int base = division(list, left, right);

		// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
		QuickSort(list, left, base - 1);

		// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
		QuickSort(list, base + 1, right);
	}
}

int main(){
	int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
	vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout << "排序前" << endl;
	for (int i = 0; i < test.size(); i++){
		cout << test[i] << " ";
	}
	cout << endl;
	vector<int> result = test;
	QuickSort(result, 0, result.size() - 1);
	cout << "排序后" << endl;
	for (int i = 0; i < result.size(); i++){
		cout << result[i] << " ";
	}
}

双指针向右移动

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
#include <iostream>
#include <vector>

using namespace std;

int division(vector<int> &list, int left, int right){
	// 以最左边的数(left)为基准
	int base = list[left];
	while (left < right) {
		// 从序列右端开始，向左遍历，直到找到小于base的数
		while (left < right && list[right] >= base)
			right--;
		// 找到了比base小的元素，将这个元素放到最左边的位置
		list[left] = list[right];

		// 从序列左端开始，向右遍历，直到找到大于base的数
		while (left < right && list[left] <= base)
			left++;
		// 找到了比base大的元素，将这个元素放到最右边的位置
		list[right] = list[left];
	}

	// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
	// 而left位置的右侧数值应该都比left大。
	list[left] = base;
	return left;
}

// 快速排序
void QuickSort(vector<int> &list, int left, int right){
	// 左下标一定小于右下标，否则就越界了
	if (left < right) {
		// 对数组进行分割，取出下次分割的基准标号
		int base = division(list, left, right);

		// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
		QuickSort(list, left, base - 1);

		// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
		QuickSort(list, base + 1, right);
	}
}

int main(){
	int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
	vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout << "排序前" << endl;
	for (int i = 0; i < test.size(); i++){
		cout << test[i] << " ";
	}
	cout << endl;
	vector<int> result = test;
	QuickSort(result, 0, result.size() - 1);
	cout << "排序后" << endl;
	for (int i = 0; i < result.size(); i++){
		cout << result[i] << " ";
	}
}