本系列文章主要介绍常用的算法和数据结构的知识，记录的是《Algorithms I/II》课程的内容，采用的是“算法（第4版）”这本红宝书作为学习教材的，语言是java。这本书的名气我不用多说吧？豆瓣评分9.4，我自己也认为是极好的学习算法的书籍。

通过这系列文章，可以加深对数据结构和基本算法的理解（个人认为比学校讲的清晰多了），并加深对java的理解

快速排序介绍 1 基本步骤1 划分操作3 快排性能分析4 快排的特性5 快排改进 51 用插入排序提高在小数组中排序性能52 选择支点pivot 快速选择算法 1首先可以估计下这个算法的大致性能2 快速选择算法3快速选择算法性能分析 重复值问题 1问题出现原因2 三路划分 21算法步骤22代码33 三路划分的快排性能 系统排序

1.快速排序介绍

快速排序是20世纪Top10算法之一。足以看出它的重要性。并且它不需要额外的空间，这是它比MergeSort厉害的地方。

1.1 基本步骤

随机对数组进行洗牌操作（重要，直接影响性能）

对数组进行分组，保证对于元素a[i]

a[i]左边的元素全都小于a[i]a[i]右边的元素全都大于a[i]

对子数组循环操作，只到完全有序

2.1 划分操作

i从左到右扫描直到发现一个a[i] > a[lo]j从右到左扫描，直到发现一个a[j] < a[lo]然后交换a[i]和a[j]

直到i和j交叉交换a[lo]和a[j]

private static int partition(Comparable[] a, int lo, int hi) { int i = lo, j = hi; while(true) { while(less(a[++i],a[lo]) && i < hi) if(i == hi) break; while(less(a[lo],a[--j])) if(j == lo) break; //可以省略 if(i > j) break; exch(a,i,j); } exch(a,lo,j); return j; }

注意这里的代码看上去很简单，但是实际上很多trick

第一是在if(j == lo)那里 判断可以省略，因为a[lo]不可能小于本身

第二个是把循环的退出条件写在循环内部

下面是我一开始写的代码。这里明显有一个问题，就是当j < i之后，这里应该立马退出循环，不然exch发生后，就出bug了。

while(i < j) { while(less(a[i],a[lo]) && i < hi) i++; while(less(a[lo],a[j])) //这里不用做边界判断因为a[lo]不会小于本身 j--; exch(a[i],a[j]); }

然后是完整的快排算法：

public class Quick { private static int partition(Comparable[] a, int lo, int hi) { /* see previous slide */ } public static void sort(Comparable[] a) { StdRandom.shuffle(a); //Important sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); } }

注意：算法开始的随机洗牌是非常重要的，可以保证算法性能最佳

1.3 快排性能分析

平均比较次数 CN=(N+1)+(C0+CN−1N)+(C1+CN−2N)+…+(CN−1+C0N)

其中 N2 表示划分概率， C0=C1=0 (下面的计算大家看看就行了，不用推……)

计算得出来 CN=1.39NlgN 实际是比MergeSort的平均比较次数多39%的，但是，快排依然快于Mergesort，因为他很多时候都是比较，但是Mergesort每一次比较都移动了元素，浪费了时间。

注意：快排的代码很容易写错，而且目前很多工具书或者网上的代码都是 O(N2) 的性能：

当数组有序或逆序的时候（没随机洗牌）

如果有很多重复键的时候（即使很随机）

1.4 快排的特性

快排是就地排序算法(没有额外空间费用)

快排是不稳定算法

1.5 快排改进

1.5.1 用插入排序提高在小数组中排序性能

即使是快排，在小数组的时候，开销也是很大的，依然可以用MergeSort中的改进方案，在小数组的时候，采用InsertionSort来提高排序速度。CUTOFF通常取10个元素

1.5.2 选择支点（pivot）

通常pivot我们选的是数组的第一个元素，但是理论上最好的piovt是刚好中间的元素，这样可以将数组二分（但是实际上对与大数据量来说，不值得在这里开销），所以一般采用 Median-of-3

2 快速选择算法

快速选择算法的目标就是给定一组数，找其中大的元素，这个在实际生活中运用广泛，比如

2.1首先可以估计下这个算法的大致性能

性能上界： NlgN ，这个很容易想到，只要排序好，取第几个元素都是简单的

性能下界： N <script type="math/tex" id="MathJax-Element-7">N</script> 至少要循环一遍

所以问题就在于能不能找到一个算法是线性时间的。

2.2 快速选择算法

快速选择算法用了快排的划分思想。

首先找个元素作为pivot

然后使得它左边元素全小于它

右边元素全大于它

然后对其中一个划分继续找（取决于j是第几个元素），直到j = k

2.3快速选择算法性能分析

快速选择算法是线性的

首先，如果每次划分的刚好是差不多一半的话，比较次数是线性的。如果每次不是一般的话，可以通过等概率求出来，也是平均线性的

3.重复值问题

快速排序有个问题，就是当它遇到重复键值的时候，性能会退化到，MergeSort没这个问题，这个问题直到1990年c的标准库中的qsort使用的快排都还有这个缺陷，而且基本所有工具书中的实现都有这个问题。

3.1问题出现原因

把所有相等的元素都放在一边了，这样，当数组中有很多重复元素的时候，划分算法基本就失灵了。

我们的代码解决方案是不管i和j只要碰到了相同元素就停下来（为什么？还记得我们代码里面全是用的less吗？相等的话不就不满足了嘛）这样基本可以保证哪怕在重复值很多的情况下，也基本是对半划分。

能不能有一个理想的算法，把所有相同的元素直接放一起呢？

3.2 三路划分

思想很简单，原来是划分成两个部分，现在改成三个部分了，是不是很像荷兰国旗？ 直到1990年中叶，传统观点都认为荷兰国旗问题不值得去做，不过现在的c的qsort和java的sort都加入了这种改进

三路划分的步骤比传统的快排划分会稍微麻烦一点点，它多了2个变量lt和gt，用来维持中间的边界。

元素大于gt边界的，都是大于V的值，

元素小于lt边界的，都是小于V的值

元素在lt和gt中间的，都是等于V的值

3.2.1算法步骤

设v = a[lo]

i 从左到右扫描，遇到hi停止

当a[i] < v 时，交换a[i]和a[lo]，然后lo和i同时+1 （放左边，lo还是指向v）

当a[i] > v 时，交换a[i]和a[hi]，然后hi-1 （放右边，lo还是指向v,i不动，因为这个时候i指向的元素变了，还要判断呢）

当a[i] = v 时，i+1 （拉大i和lt的距离，扩大lt和hi的空间）

算法运行完的结果（可以自己跑一下，看demo:7-3）：

3.2.2代码

你可以发现其实这个代码很精巧

private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int lt = lo, gt = hi; Comparable v = a[lo]; int i = lo; while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) exch(a, lt++, i++); else if (cmp > 0) exch(a, i, gt--); else i++; } sort(a, lo, lt - 1); sort(a, gt + 1, hi); }

3.3.3 三路划分的快排性能

总而言之一句话，它在实际应用中性能很棒，效率很高，是熵最优的。

4. 系统排序

＞排序在实际的应用中十分广泛

java中使用的主要是快排处理基础类型，mergesort处理对象类型

我们之前说过了，快排有一定的缺陷，所以有人花了大功夫改进了快排算法，也是现在C，C++, java中广泛使用的

但是尽管这样，快排还是有缺陷

目前在不同领域有不同的适用的算法

但是没有一种算法能覆盖所有应用，也许快排在大多数排序应用中都是很好的选择，但是它毕竟是不稳定的，而且在一些特殊情况下，性能不会特别好，还可能会出现一些致命的错误。

所以要学会去评价一个算法的优劣和是否适合自己的应用，以及如何能够改进算法使得它更好的适应自己的应用。