教你面试时不会忘记的5种手写排序
大家平时面试的过程当中遇到排序算法会比较慌乱。这是因为排序算法的种类繁多，高德纳所编写的《计算机程序语言的艺术》当中，排序算法就会占掉近千页的比重。好比大千世界的物质，虽然缤纷多姿但是元素只有100多种；排序算法虽然丰富多彩，但是排序的进步方式并没有很多。所谓进步，就是算法一点一点去接近目标结果的过程——无论你要排序多大的一个数组，最终你还是需要中间的过程，一点一点让你这个数组越来越有序。最终到达完全的有序状态——这就是进步。
归根结底，排序的进步方式大概有下述三类。
- 增加一减少一,可称之为加1法。或减1法。
- 将原问题拆分成一个个规模更小的子问题。分别解决，再将结果合并。这就是分治法。
- 利用数学关系、。将问题从无序状态直接映射到有序状态。这是加一法的一种特例。我们称之为哈希法
关联面试题目：
- 写一个插入排序？
- 写一个冒泡排序？
- 写一个快速排序？
- 写一个合并排序？
- 给定0~99之间的数字，怎样排序最快？
- 只有0,1,2的数组，怎样排序最快？
加1法、减1法
当你一个人打扑克抓牌的时候，桌面上倒扣者扑克牌堆，是无序的集合。你每抓一张牌到自己的手里，开始整理，就从无序的集合中拿走了一张牌；你的手里牌，是一个有序的集合。从无序到有序的过程，就是进步(progress)。
每次抓牌，有序的集合就多了1张牌（加1法），无序的集合就减少了一张牌（减1法）。有加就有减，加减1是一种方法。
插入排序
按照抓牌这个例子，设计出来的算法我们称之为插入排序（insertion sort)。
我将插入排序列为你的第一个学期目标，这是因为它足够直观。假设有一个数组A需要排序。我们用循环变量i 分隔有序、无序的集合，如下图。一开始，循环变量i 等于0，代表着有序的集合，目前数量是0；而无序的集合，目前是A.length。
算法是一个i 逐渐从左向右移动的过程，也就是从i等于0增加到A.length - 1的过程。
先用伪代码去描述一下我们的思路：
void insertionSort(A){
for(int i = 1; i < A.length; i++) {
// 将A[i] 插入在卡片0，到卡片i之间
}
}
上面的程序，我们一开始i是0。然后每次for循环，我们进行加1法。i左侧是有序的集合，右侧是无序的集合。每次循环执行完成之后，有序的集合加1，无序的集合减1。构成了我们算法的进步，**这种每次完成循环之后，必然会进步的条件，我们也称之为循环不变式(loop invariant)。**现在我们这个for循环的循环不变式，就是循环结束，脚标小于i 的元素，都处于了有序状态。i 总是指向下一个无序的元素。
有了这样一个最基本的进步框架，我们下来思考，每一次for循环中我们应该使用怎样的一个具体的算法。具体的算法就是像插排一样，每一次我们把A[i]这一张卡片。插入到A[0]到A[i]之间。根据这个思路，我们不难写出。最终的解决方案。
public class InsertionSort implements IMutableSorter {
@Override
public void sort(int[] A){
for(int i = 1; i < A.length; i++) {
// 将A[i] 插入在卡片0，到卡片i之间
// j代表抓到的牌，先放到最右侧，不断交换到对应的位置
int c = A[i];
int j = i;
for(; j >0 && A[j-1] > c; j--) {
A[j] = A[j-1];
}
A[j] = c;
}
}
}
在上面这段程序当中，内层循环整体在做加1法，也就是将第i张牌纳入已排序的集合。内存循环的做法。如下图所示。
16是我们要插入的牌。具体的做法是将19覆盖16。再将18覆盖19。最后因为15已经比16小了。将16放到原来18的位置。
在实现上述插入排序程序的时候，测试用例。来验证这段程序是否写对。测试用例如下：
void sortTest(Class cls, int N){
var constructor = cls.getConstructor();
var inst = (IMutableSorter)constructor.newInstance();
var start = System.currentTimeMillis();
inst.sort(A);
System.out.println("time usage:" + (System.currentTimeMillis() - start));
assertSorted(A);
}
@Test
public void test_insertionSort(){
sortTest(InsertionSort.class, 100000);
}
视频的链接。这段测试程序我们用了反射。目标是让这段测试程序可以测试更多的排序算法。同时我们在这段测试程序中，计算了时间。如果你对这段程序有所疑问。还请你观看视频中我的手把手教学，我会一行一行将你把这个测试程序敲出来。
冒泡排序(Bubble sort)和选择排序(Selection sort)
另外两个加1法的典型代表。就是冒泡排序(bubble sort)和选择排序（selection sort)。这两个排序的循环不变式。非常的相似。和插入排序是一样的。每次排序一个元素。有序集合加1，无序集合减1。因此我们仍然需要一个循环变量i。去控制有序和无序之间的边界。
这次我们换一个方向。我们让有序集合，从右向左增长。当然你也可以让有序集合从左向右增长。这其实并不重要。伪代码如下。
bubbleSort/selectionSort(A){
for(int i = A.length-1; i>=0; i--){
// 找到0到i间的最大元素放入最右边的位置A[i]中
}
}
上面的两段伪代码几乎一模一样。你可以把冒泡牌去看成选择排序的一种特例。我们先说选择排序。我们每次循环的时候。我们找到0到i位置中最大值。然后将它放入位置A[i]。
下面是选择排序的。完整代码。
public class SelectionSort implements IMutableSorter {
@Override
public void sort(int[] A) {
for(int i = A.length - 1; i >= 0; i--) {
int j = maxIndex(A, 0, i+1);
Helper.swap(A, i, j);
}
}
static int maxIndex(int[] A, int i, int j) {
int max = Integer.MIN_VALUE;
int maxIndex = i;
for(int k = 0; k < j; k++){
if(max < A[k]) {
max = A[k];
maxIndex = k;
}
}
return maxIndex;
}
}
大家在实现排序算法的时候可以参考我这样的思路，对于复杂的计算最大值脚标的函数在单独实现一个单独的静态的方法。这样计算最大值脚标的函数，就可以单独测试。而且整个程序阅读起来。就会非常的容易。书写和思路也会非常的模块化。以上程序。也可以在面试中。写给面试官。将一段逻辑拆分成不同的部分去处理，可以体现自己的基本功以及工程化能力。
我们用同样的方法对上面这段程序进行测试，测试代码如下。
@Test
public void test_selectionSort() {
sortTest(SelectionSort.class, 100000);
}
接下来请你思考一个问题。上面这段程序。如果对下面这个数组。进行排序。
2 2 1 1
第1个2，和第2个2相对顺序是否会发生改变。这是因为，排序背后实际承载的意义是我们的业务。
比如说我们的商品卡片，如果我们按照时间紧排序。我们希望时间相同的卡片，原本的顺序是没有发生变化的。**这种原本同值已有的顺序不会再发生变化的排序，我们称之为稳定的排序。**上面序列，如果用选择排序，两个2之间的相对顺序会进行交换。因此，选择排序不是一个稳定的排序。你可以思考，插入排序，是不是稳定的排序——你会得到结论，插入排序是一个稳定的排序。
这里给你留个课后思考：测试排序的稳定性，用例如何写？欢迎在答疑区和群里交流。
稳定的排序在我们处理实际问题的过程当中更有意义。通常我们都愿意用稳定的排序。那么我们如何去修改选择排序让他变成一种稳定的排序呢？
这时我们就可以考虑用一种非常相似的过程实现选择，这就是冒泡排序（bubble sort)。主循环不变式依然没有发生变化，每次我们挑选出从0到i之间的最大值元素放到最右边。只是我们将挑选的方法从选择一个最大的数放到最右边，变成不断的进行元素交换。
像上图中这样一段序列，如果我们从左边开始。两两进行比较，每次只有左边的数大于右边的数的时候，我们才进行交换。如果左边来说想右边数，那么就不变。3和7，不会发生交换。7和2会发生一次交换，而7和1会发生一次交换，最终。最大的数7会在最右的位置。
这个算法。就是冒泡排序。用这样的方式，我们可以选出一个最大值放到最右边。然后我们每次只选出一个最大值，让有序集合加1无序集合减1。具体的程序如下。
public class BubbleSort implements IMutableSorter {
@Override
public void sort(int[] A) {
for(int i = A.length - 1; i >=0; i--) {
// 找到0-i间的最大元素放到A[i]
bubble(A, 0, i+1);
}
}
static void bubble(int[] A, int i, int j) {
for(int k = i; k < j - 1; k++){
if(A[k] > A[k+1]) {
Helper.swap(A, k, k+1);
}
}
}
}
在上面完整的程序当中。我们依然采用抽象出一个子过程，叫做bubble的方法。虽然我们在实现算法库的时候，为了减少一次函数调用。我们不会。再去抽象一个子过程。但我依然建议你。先写出这个版本。让他更符合人的思想。以及直觉。然后再进行优化和合并。上面这段程序。每一次bubble方法。负责将0到i间的最大元素。用冒泡的方式。也就是逐个比较的方式。像水里边的气泡一样冒到最右边。这就是冒泡排序。
你可以再思考一下。2 2 1 1 序列的。例子。你会发现，第二个2，会进入最右边。因此，冒泡排序是一个稳定的排序，不会打乱原本等值元素之间的顺序。
分治策略
接下来我们讨论另一类排序算法，就是分治策略（Divide And Conquer)。当你打扫三居室的时候，你会先将这个三居室分成若干个房间。然后你分别每个房间去打扫。对于每一个房间，你又会分成书桌床、柜子。各种各样的部分再分别进行打扫，这样你就将问题分成了好几个层级。
对于第一层级来说，是逐个房间的打扫。所以第一层级的进步方式，是逐屋的。对于第二层级，你是将房间又进行了一次划分。所以第二层级的进步方式，是逐房间、区域的。最后才到你最小的打扫单位，比如说书桌上的显示器，键盘等等。
我们排序也可以利用类似的进步思路，比如我们要排序一个完整的数组。我们可以认为我们先排序数组的左半部分。在排序数组的右半部分，对于数组的左半部分。我们再去排序他的左半部分和右半部分，直到我们拆分出只有一个大小为一的数组，这个数组就是排好序的，因为它只有一个元素。
对于第一层级。原数组的那半段已排序的数组。当这两个数组都分别排好去之后，我们要将这个数组进行组合。其实这样的思路不仅仅适用于第一层级。而是适用于你的每次思考。
如下你的每次思考都是从当前的问题开始。将问题拆分成两个等大的子问题。然后在此问题处理完之后，再将子问题的结果进行合并。这样就解决了原本的问题。
这样的思考可以一直在延续。就像下面这张图这样。以至于无穷无尽。直到规模变得非常非常小，比如说一
因此我们可以写出一个通用的分治策略的伪代码。
solve(A, a, b) {
if(b - a == 1) {
return;
}
mid = (a + b + 1) / 2;
solve(A, a, mid);
solve(A, mid, b);
merge(A, a, b);
}
在上面这段程序当中，solve这个函数解决的是脚标由a到b之间的数据。当只有一个数据的时候，直接返回。而两次递归调用的solve是在分治解决。被平分成两半的子问题。最后的merge函数，在合并两次solve的解。
当然，分治策略不一定是平分成两半。有可能是平分成三份，或者四份；另外，还有的分治策略算法并不需要合并。
合并排序（Merge Sort）
在上面这样的思路下，我们可以来构造一种最符合直觉的排序方式。我们称之为合并排序。我们每次将原序列拆分为两个等待的子序列，然后我们再分别解决这两个等待的子序列。每个子序列在拆分成两个等待的子子序列。这样无穷无尽，直到问题的规模为1的时候，我们不再递归向下。
每一个递归节点，有一个问题的拆分过程，就会有一个问题向上合并的过程。向上合并的过程当中，我们拿到的是两个已经排好序的子序列，我们要将这两个子序列合二为一。
因此我们整体的程序。框架类似下面这样：
// A排序的数组
// l: 左索引（闭区间)
// r: 右索引（开区间）
private void mergeSort(int[] A, int l, int r) {
if(r - l <= 1) {
return;
}
int mid = (l + r + 1) / 2 ;
mergeSort(A, l, mid);
mergeSort(A, mid, r);
merge(A, l, mid, r);
}
上面这段程序，每次对merge sort的调用，会引发两次分治调用。两次只调用结束之后，我们认为，被拆分成两半的子问题，就已经得到了解决。所以最后我们的merge函数，会去合并两个子问题的解。
上述程序中，l和r是区间角标，l是一个闭区间；r是一个开区间。这种左闭右开的结构。非常适合遍历，比如说对for循环的书写很有帮助。比如你可以写出下面这段程序去遍历数组。
for(int i = l; i < r; i++) {...}
mid是计算出来的中间位置。
合并过程
最后我们来说说合并的过程，合并的过程。没有办法在原数组上直接进行。我们需要将原数组左半部分，拷贝到数组B中，右半部分拷贝到数组A中。
如下图所示，我们还需要两个循环控制变量。i代表，B中下一个需要选择的值。j代表C中下一个需要选择的值。当B[i] < C[j]时，说明下一个我们应该从B中选择，选完这个值的时候我们应该把i加1。
在B和C的最后面，我们还追加了一个Max值，这个Max值我们称之为哨兵。哨兵的作用是让我们减少对边界条件的判断。这个Max值我们可以取整数的最大值，这样比较的过程中，在B和C的值全部读完之前，都不会取到这个Max值——这样就节省了边界条件的判断。下面大家可以看一下完整的程序。
public class MergeSort implements IMutableSorter {
@Override
public void sort(int[] A) {
mergeSort(A, 0, A.length);
}
private void mergeSort(int[] A, int l, int r) {
if(r - l <= 1) {
return;
}
int mid = (l + r + 1) / 2 ;
mergeSort(A, l, mid);
mergeSort(A, mid, r);
merge(A, l, mid, r);
}
private void merge(int[] A, int l, int mid, int r){
int[] B = Arrays.copyOfRange(A, l, mid+1);
int[] C = Arrays.copyOfRange(A, mid, r+1);
B[B.length-1] = C[C.length-1] = Integer.MAX_VALUE;
int i = 0, j = 0;
for(int k = l; k < r; k++) {
if(B[i] < C[j]) {
A[k] = B[i++];
} else {
A[k] = C[j++];
}
}
}
}
快速排序(Quick Sort)
还有一种比较典型的分治策略排序算法，就是快速排序（Quick sort)。快速排序，并不是将问题规模一分为二。
快速排序对问题的拆分具有一定的随机性；快速排序要求我们在原问题中任取一个元素。将大于这个元素的值放在这个元素左边，将小于这个元素的值放在元素右边，这样就构成了两个子问题。
上图就是快速排序的核心思路。x是我们选出的一个随机的元素。当然你也可以固定某一种对x的选择方法。比如说每次选择问题的第一个元素或者每次选择问题的最后一个元素。或者每次选择问题最中间的元素。但是这并不重要。选择好x之后，我们将小于x的值都放到x的左边。把大于x的值都放到x的右边。这样下去。我们最终会将原问题排序。
在这样的分析方法当中，快速排序的正确性。
我们可以换一种角度来思考。当我们拆分到最小粒度的时候，问题的规模可以到达1。因此，最小粒度的时候。快速排序成功了。然后当我们在扩大粒度的时候，比如说问题规模是3，因为两个子问题都有序了。所以规模是3的问题，通过快速排序得到了解决。
通过这种方式，依次类推，规模是5的问题也可以解决，规模是7的问题也可以解决。因为规模是5的问题，会拆分成一个规模是3的问题，加上一个规模是1的问题。而规模是7的问题，会拆分成两个规模是3的问题。通过这种方式，我们逐渐可以推出任何一个规模的问题都是可以解决的。这种思考方式我们称之为归纳。
我并不想把太多的数学带入给大家，比如说告诉大家这个叫做数学归纳法。我说他是归纳是因为归纳是人类的一种思维方式。当我们看到太阳今天升起来，明天也升起来时候，我们归纳出太阳每天都会升起来，这是我们通过本能感知到的结论。我们通过很小的问题逐渐将这个问题归纳的越来越大，去解决更大的问题。这是一种反向的去推导的思考方式，这种方式就是我们的归纳。
我们对快速排序有了一个最基本的认识，我们就可以来构造它的写法。快速排序是一个只需要拆分但是不需要合并的排序算法。我们先写出这个算法的框架。
void quickSort(int[] A, int l, int r) {
if(r - l <= 1) {
return;
}
// 选择最左边的元素构造子问题集合
// 小于x的放到左边，大于x的放到右边
// int x = A[l];
// i代表x的位置
int i = partition(A, l, r);
// 省略计算x所在位置i
// 以及将所有小于x的元素放到左边，大于x元素放到右边的
quickSort(A, l, i);
quickSort(A, i+1, r);
}
上述程序构成了一个快速排序的框架。最前面的if是快速排序的终止条件。所谓终止条件，就是执行到问题规模是1（或更小）的时候，快速排序就停下来。因为规模是1的问题，是已经解决的问题。
当规模大于1的时候，快速排序需要找到一个支点x。让左边的元素小于x。右边的元素大于x。我这里选的支点x就是第0个位置，你可以选其他的位置。这并不重要，当然0位置有一定方便之处，这种方便后面你会体会到。
然后我定了一个整数变量i，这个变量i代表了x最终所在的位置。x一开始是在第0个位置。但是因为小x的元素都放到了左边,大于x元素都放到了右边。最终x会停留在某个位置，这个位置就是i。这个计算过程我们先不把它写出来。我们先写出最后的两行递归。当确定了x的位置之后，我们将原问题拆分成两个子问题。并且进行递归，以上就是快速排序的框架。写程序一定要能够写出一个框架。这个框架就是我们处理问题的思路，如果我们一直这样坚持思考，也许有一天，哪怕是写汇编程序。你也可以，迅速给出一个非常有逻辑的程序。但是在我们训练之初，我们应该遵循这样的写法。也许以后你会到达看山不是山，看水不是水的水平，那就是以后。事情了。
书写了这个框架之后，我们再来思考，如何把小于x的数据都放到x左边？把大于x数据都放到x的右边。
方案1（Immutable实现）
接下来我们先来尝试一个简单的方案。程序也比较好写。这个方案就是我们利用筛选器，将a中所有小于x的元素。大于x的元素、等于x的元素都筛选出来。
这样去处理问题，让我们整个程序都变得比较好写。但是这也让我们快速排序的实现，从在原数组上进行改写，变成了需要使用链表操作。
你可以先阅读下下面的程序，如果感觉到阅读起来有困难可以观看我的视频，视频中会带你一行行写一遍。
然后请你思考这个问题：为什么我会用链表作为集合，这是因为将两个链表连接起来的操作可以在非常短的时间内完成。具体我们会在讲链表的一节和大家讨论。
public class QuickSort implements IImutableSorter{
@Override
public List<Integer> sort(List<Integer> A) {
return this.quickSort(A);
}
private List<Integer> quickSort(List<Integer> A) {
if(A.size() <= 1) {
return A;
}
var x = A.get(0);
var left = A.stream().filter(a -> a < x)
.collect(Collectors.toList());
var mid = A.stream().filter(a -> a == x)
.collect(Collectors.toList());
var right= A.stream().filter(a -> a > x)
.collect(Collectors.toList());
left = quickSort(left);
right = quickSort(right);
left.addAll(mid);
left.addAll(right);
return left;
}
}
上面的方案不能在原数组上进行操作，而且需要很多拷贝操作。因此我们可以思考另外一个更好的方案，而且你现在可能还不知道什么叫做时间复杂度。我会在本节课结束之后，以文档的形式为大家扩展关于时间复杂度的阅读资料。你可，学习完下一讲内容之后，再来回顾我们书写的各种排序方案的时间复杂度。
方案2
作为方案2。我们希望整个程序能够更简洁一些，并且我们不希望在定义中间的数据结构，比如说像方案一中，我们需要多定义好几个链表。多定义数据结构代表着我们需要多消耗内存空间。而对原数组进行筛选本身也要消耗更多的时间。
在方案二中，我们会复用加1法。当我们需要根据某一个值。将原问题进行拆分。会形成下图中的思考模型。
我们始将整个问题拆分成三部分，一部分是小于x的值。一部分是大于x值，还有处于中间的状态，就是我们还不能确定的值。
我们用循环变量i、j来作为三段区间的分水岭。在算法的开始支出。整个问题都是不确定的，这个时候i等于1，j等于数组的长度（因为第0个元素是支点）。然后我们开始构造一组进步的条件：每一次不确定的值都会减少1；相对的小于x的值会加1，或者大于x值会加1。
具体的程序如下。
int partition(int[] A, int l, int r) {
int x = A[l];
int i = l + 1;
int j = r ;
// i = j 意味着不能确定的值个数为0
while(i != j) {
if(A[i] < x) {
i++;
} else {
swap(A, i, --j);
}
}
swap(A, i-1, l);
return i-1;
}
上面的程序每次while循环。会让i+1或者j-1。相当于每次让不确定的只减少一。思考清楚ij的具体含义，就是加1法的终极奥义。所以我们在重新的review一下i和j的具体含义。如果去模糊的思考。i和j刚好是三段值的分水岭。但是如果我们要想的更细致一些。每次循环结束的时候，i从左边指向下一个不能确定的值。j从右边指向下一个不能确定的值。当i，j相遇的时候，也就是while循环结束的时候。因为这个时候已经没有不确定的值了。
下面是整个quick sort的程序。你可以从我的git项目中拿取代码。也可以将它拷贝到你的IDE中执行
public class QuickSort1 {
public void quickSort(int[] A, int l, int r) {
if(r - l <= 1) {
return;
}
// 选择最左边的元素构造子问题集合
// 小于x的放到左边，大于x的放到右边
// int x = A[l];
// i代表x的位置
int i = partition(A, l, r);
// 省略计算x所在位置i
// 以及将所有小于x的元素放到左边，大于x元素放到右边的
quickSort(A, l, i);
quickSort(A, i+1, r);
}
private int partition(int[] A, int l, int r) {
int x = A[l];
int i = l + 1;
int j = r ;
// i = j 意味着不能确定的值个数为0
while(i != j) {
if(A[i] < x) {
i++;
} else {
swap(A, i, --j);
}
}
swap(A, i-1, l);
return i-1;
}
static void swap(int[] A, int i, int j) {
int t = A[i];
A[i] = A[j];
A[j] = t;
}
}
下面是我构造的测试用例。
@Test
public void test_quicksort1(){
sortTest(QuickSort1.class, 100000);
}
@Test
public void test_quicksort(){
sortTest(QuickSort.class, 100000);
}
合并排序和快速排序的时间复杂度
在进入下一个环节之前，我们对分治策略进行一个简单的总结。所谓分治策略，就是先将问题拆分成子问题，解决完子问题再合并子问题的结果。合并子问题结果这一步不是必须的。你可以看到，在快速排序当中。我们并没有合并子问题的结果。
那么分治策略的性能怎么样呢？下面讨论如何看不懂，请你在确认在学习了下一节我对时间复杂度的补充讨论之后，再来看这部分。
分治策略的性能，可以分成三部分来思考：
- 拆分子问题的时间
- 分别处理每个子问题的时间
- 合并子问题的时间
递归的时间复杂度，也必须递归的思考。
按照这个思路，我们先来讨论一下归并排序。
- 拆分时间：对于一个规模为n的问题，拆分成两个子问题的时间只需要进行一次角标的。计算，所以这个时间是O(1)。用时记为常数d。
- 合并时间：将两个已经排好序的数组进行合并。我们需要将这两个数组同时拷贝。然后再用一个for循环恢复原数组的值。在这个过程当中，循环次数和规模的大小成正比。合并时间可以记为T=c*N，c是一个常量，N是问题的规模。因此是O(N)的时间复杂度。
我们按照上述的关系，用T代表处理规模为N的问题需要的时间。那么我们可以得到一个数学关系：
T(N) = d + c_N + 2_T(N/2) ≈ cN + 2T(N/2)
这个数学关系看上去比较复杂。所以我把他画成一张图，帮助你理解。在这个关系当中。拆分的时间d无关紧要我们把它去掉。
按照上面的关系，第1级需要的时间是cN。第2级需要的时间是两个子问题时间加起来依然是cN。第3级依然是cN。直到最后一级依然如此。
按照这个关系，最终我们的时间就是：T = H*cN，H是层的数量。
而我们这样总共分成多少层呢？那就要问，问题被减半减半，一共可以分多少次？这刚好是指数运算的逆运算。也就是对数运算。T = logN * cN = cN log N
从时间复杂度上我们将它记为，O(NlogN）。
按照这样的思考方式，忽略掉常数时间，当N非常大的时候，logN也不会很大，所以这样的排序算法的时间复杂度是相对较低的。
快速排序也可以使用相同的分析方法。如果不想陷入太复杂的分析过程，可以进行近似的分析。如果每次我们选取了一个值之后，将原问题拆成两半。左边一半和右边一半，究竟有多少？当然每次都可能不同，因为随机的。但是这种拆分就好比抛硬币一样，当我们的次数多了，整体来说就会趋向于平均。因此我们可以把快速排序看做一个没有合并过程的合并排序。
只不过快速排序，将问题拆分的时间复杂度是O(N)。因为partition函数会对数组中的所有元素进行遍历。所以快速排序也可以画出类似上图中的树状结构。快速排序平均执行时间是O(NlogN)。
这里再给你留一道需要思考的题目：快速排序的最坏情况什么时候出现，复杂度多少？
哈希函数
在排序这个领域，还有一类进步的方法。本质上也是一次处理一个问题，你可以认为是加1法。只不过它的使用方式有点特别。
桶排序（Bucket Sort)
我们以桶排序为例，假设我们要排序100万个0~99之间的数字。那么什么样的排序方法是最优的呢？
这个时候我们如果使用合并排序或者快速排序可以达到较快的速度。如果你配合我的视频一起执行过合并排序或者快速排序的程序，你会发现10万量级的数据只要在毫秒级别就可以执行完成。
但是有没有更快速的排序呢？插入排序冒泡排序和选择排序因为需要两层循环，复杂度都是O(N^2)，速度慢。
所以这里其实我们有一个更好的方法。我们设计100个桶，每个桶对应。不同值的数字。第一个桶对应0，第100个同对应99。
对于一个要排序的数字X，我们可以通过X % 100去计算他属于哪个桶？
我们可以通过一次遍历，将这1万个数字都放入对应的桶中，这样就相当于将数据排好序了。
具体程序如下：
public class BucketSort {
public List<Integer> sort(List<Integer> A) {
int k = 100;
var buckets = new ArrayList<LinkedList<Integer>>();
var list = new ArrayList<Integer>();
for(int i = 0; i < k; i++) {
buckets.add(new LinkedList<Integer>());
}
// 放入桶中
for(var item : A) {
buckets.get(item % k).add(item);
}
//从桶中取出值
for(int i = 0; i < k; i++) {
list.addAll(buckets.get(i));
}
return list;
}
}
上面的程序之所以可以用item%k计算桶的序号，是因为我们知道A中的全是0~99的数据。如果我们不确定数据值的范围，这里就需要一个更加一般的方法。比如我们事先知道数据的最大值和最小值是max和min，可以修改上面的程序：
public class BucketSort1 {
public List<Integer> sort(List<Integer> A, int k, int max, int min) {
var buckets = new ArrayList<LinkedList<Integer>>();
var list = new ArrayList<Integer>();
var D = max - min + 1;
var quickSort = new QuickSort();
for(int i = 0; i < k; i++) {
buckets.add(new LinkedList<>());
}
// 放入桶中
for(var item : A) {
var key = (item - min) * k / D;
buckets.get(key).add(item);
}
//从桶中取出值
for(int i = 0; i < k; i++) {
list.addAll(quickSort.sort(buckets.get(i)));
}
return list;
}
}
(item - min) / D 计算A[i]占整体数据的比例，再乘以k，就是将数据按照比例映射到桶中，这是一种几何上线段长度的关系。你可以把item想象成min到max之间的某个点。计算好item的比例关系。再乘以桶的数量。就相当于说，将item(A[i])放到了对应的桶中。下面我画了一张图来帮助你进行理解。
还有一个改动的地方.,这就是加入到同一个桶的数据不再是单一的值。因此，我们需要对桶中的数据进行排序。上面我用快速排序对统中的数据进行排序,所以每个桶都经过了一次快速排序。
以上就是完整的桶排序的程序。
其实这里还有很多的问题。可以和大家讨论，比方说到底应该不应该用快速排序。再比方说，如何针对数据规模选择桶的大小？那么这些讨论我们结合对桶排序的时间复杂度和你一起讨论。
桶排序的时间复杂度
对于我们写的第一个桶排序程序。数据是0~99之间的数值。这种情况下你会发现，时间复杂度非常好计算。因为上面虽然有常数个数的for循环，你会发现每个for循环。最大的循环次数。不会超过数据本身的规模，所以是O(N)。
第二个桶排序是一个一般的桶排序。关键的变动点在于，最后一个for循环似乎因为使用了快速排序。导致了时间复杂度的变化。如果所有的数据都被映射到一个桶中，那就意味着整个桶排序时间复杂度变成了O(NlogN)。（如果你不理解为什么是这样？请你阅读一下我的补充资料，也就是下一节关于时间复杂度的介绍。）
如果数据被平均拆分成了k个等大的子问题，每一个的时间复杂度是O(N/klog(N/k))。这里。如果我们把k做一个常数，那么这个时间复杂度就是O(NlogN)，因为时间复杂度的计算，我们是要忽略常数。如果我们把k看做一个和N成比例的值，也就是N/k=C，C是一个常数。那么时间复杂度就变成了k * O(N/klog(N/k)) = k * O(clogc) = O(k) = O(N/C) = O(N)。如果你不理解这是如何转化而来的。
也请你阅读一下下一节我的补充资料。多说一句，之所以有这样的换算，是因为时间复杂度需要忽略常数。时间复杂度是对规模随着时间增长而增长的关系的一种分类。每一种时间复杂度的类别应该具有代表性，因此需要忽略掉常数。这种思考并不是从数学的推理中得到的，有很多的教材。在这里教大家如何用数学的方式去推导出时间复杂度这种忽略常数的关系。而事实上不应该这样去做，因为这是我们的需求。是因为有需要忽略掉常数去分析算法的需求，所以才从数学上设计了时间复杂度。数学只是工具，本质是因为我们希望有这样一个需求。所以大家在学习算法的时候，如果你理解了他的设计思路，并不理解他的数学关系。这种情况下，你是可以从另一个角度去把算法问题想清楚，包括神经网络。但是反之你理解了数学关系。并且你尝试用数学关系去证明需求。那这就和我们研究这些问题的本页背道而驰。
包括这个世界有的比如说相对论先有了观察到的现象——观察到了光速不变，才发明了相对论去描述这一现象。这才是解决问题的本质。事实上，当年爱因斯坦他的数学也不是非常的好，所以他发明相对论的数学公式。是在他朋友的帮助之下才做完的。再多说一句。发明C++之父写 STL库时（你可以理解成。是Java集合库的前身。）也是在数学家的帮助下完成的。
我说这些是希望你提升自己能够提出需求去解决问题的能力。当你拥有了提出问题并且尝试解决这些问题的能力的时候，具体解决问题需要用到的工具，你是可以依托其他的力量的。
总结
总结一下。这节课我们学了三种构建排序程序的方法。这三种方法甚至可能会出现合并起来，组合在一起使用的情况。他们是：
- 加1/减1法
- 分治策略
- 哈希函数
我希望你可以灵活的掌握这三种方法。
第一种方法，最重要的是掌握对循环变量、循环不变式的分析。我希望你以后写循环的时候，可以清楚的说出每个循环变量它的实际意义。并不是为了循环而循环。
第二种方法，分治策略。本质上是递归。递归的本质是归纳。人拥有归纳的思考方式，人拥有递归的思考方式。我们看到一棵树。并不是尝试。为他的每一个部分。都取名字。我们是将数进行分类。比如说分成树干。树枝树叶。而树枝就是一个递归的定义。在分治策略当中，你会惊奇的看到。将原来的问题拆分成几个子问题去解决，会提高算法的执行速度，这是一件非常奇妙的事情。但是我不建议你用数学去理解他，这个是我们观察到客观世界的规律。并不是因为数学上证明了有这样的数学关系。而是因为世界本身就是这样的。第三种方案哈希函数。我们通过数学的关系。直接将一个值映射到它应该在的位置。这种方式。虽然你可以认为是一个一个在做，因此他是加1法。其实区别非常的大，因为这是一种映射关系。所谓的映射关系。就是他可以延迟执行，甚至不执行。映射是一种描述，你可以理解为数据，并不是一个过程。
在你面对实际问题的时候，你可能会根据自己的诉求去选择不同的算法。特别是稳定性。我顺便也留一道思考题。我给出的以第一个元素为支点的快速排序算法。目前还不是一个拥有稳定性的算法。请你进行思考。看看如何进行简单的修改。将它修改为一个具有稳定性的算法。
另外，请你再多进行一步思考。我最后给出的桶排序的算法，是不是一个拥有稳定性的算法？
好的，这节课就到这里。如果你对这节课的时间复杂度讨论有所疑问。请你阅读一下下一节课的补充资料。时间复杂度。