快速排序

缘起

不客气的说, 快排已经是几乎每个库（c++ STL、java collection 甚至一些js库）中必备的API了, 由此可见其重要性.

快排是与堆排一样常用的内排序算法,但是更加简洁
快排属于交换排序（冒泡是另一种交换排序的初级版，但是冒泡稳定，快排不稳定(涉及不相邻元素的调换的排序都是不稳定的,例如希尔，堆排)），堆排属于选择排序（简单选择排序是另一种初级版，但是初级的选择排序与堆排都是不稳定的）
在时间复杂度上，快排可能最差到O（N^2）但是堆排一直很稳定O(N*logN)

分析

快排和冒泡一样都属于交换排序, 但是之所以比冒泡快是因为交换元素之间的距离大，代价是不稳定（而冒泡一直是相邻元素交换，所以稳定）.

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
61
62
#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <cstdlib>

#pragma warning(disable:4996)

//#define LOCAL
using namespace std;

// 对 a[lb,...,ub] 做快排
void qsort(int *a, int lb, int ub)
{
	if (lb > ub) return; // 只有一个元素排个屁
	int pivot = a[lb]; // 轴
	int i = lb, j = ub; // 左哨兵和右哨兵位置
	while (i<j) // 只要左右哨兵没有碰面
	{
		while(i<j&&a[j]>=pivot)j--; // 必须右哨兵先移动，想一个例子就是8,1,2,3,4,5,6,7,9如果左哨兵先移动，则i=8,j=8,则a[8]=9直接飞到a[0]去了，这不就坏了.而右哨兵先移动的话,j变成索引7,则i就变不成8）,如果>=基准数（代表位置放的正确）就继续，本质上是因为这里pivot的选取是从a[lb]开始的	
		while(i<j&&a[i]<=pivot)i++;
		if (i<j) swap(a[i],a[j]);
	} // while结束之后, i就是轴点位置, 所以a[i]要是轴点的值才行
	a[lb] = a[i]; // lb 为原先的i的值
	a[i] = pivot; // a[i]为轴值
	qsort(a,lb,i-1); // 递归
	qsort(a, i+1, ub);
}

void shuffle(int *a, int lb,int ub) // 对 a[lb,...,ub] 进行随机洗牌
{
	srand(time(0));
	int len = ub -lb+1;
	for (int k = 0; k<500; k++) // 500次洗牌
	{
		int i = lb + rand()%len;
		int j = lb+ rand()%len;
		if (i==j) continue;
		a[i] = a[i]^a[j];
		a[j] = a[i]^a[j];
		a[i] = a[i]^a[j];
	}
	
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif

	int a[14]={13,1,2,3,4,5,6,7,8,9,10,11,12,14};
	shuffle(a, 0, 13); // 洗牌
	puts("排序前:");
	for (int i = 0; i< 14; i++) printf("%d ", a[i]);

	qsort(a, 0, 13);

	puts("排序后");
	for (int i = 0; i<14; i++) printf("%d ", a[i]);

	return 0;
}

注意, 快排的复杂度最坏是O(n^2)，因为上面 8 1 2 3 4 5 6 7 9 就是例子.

实际写算法的时候, 一般也不会自己写快排, 而是使用 c++ STL 的 sort函数，详见【1】

参考

【1】https://yfsyfs.github.io/2019/05/25/%E6%97%A0%E5%90%91%E8%BF%9E%E9%80%9A%E5%9B%BE%E7%9A%84%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91-MST-%E4%B9%8BKruskal%E7%AE%97%E6%B3%95/