冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤$1$~$3$，直到排序完成。

稳定性

在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。

适用场景

冒泡排序思路简单，代码也简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。

选择排序

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

稳定性

用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。 不过，一般提到排序算法时，大家往往会默认是数组实现，所以选择排序是不稳定的。

适用场景

选择排序实现也比较简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。但是，由于固有的$\mathcal O(n^2)$复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序。

插入排序

1. 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
2. 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
3. 重复上述过程直到最后一个元素被插入有序子数组中。

稳定性

由于只需要找到不大于当前数的位置而并不需要交换，因此，直接插入排序是稳定的排序方法。

适用场景

插入排序由于$\mathcal O(n^2)$的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。例如，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的实现中，当待排数组长度小于$47$时，会使用插入排序。

归并排序

两种方法

• 递归法（Top-down）

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤$3$直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

• 迭代法（Bottom-up）

原理如下（假设序列共有$n$个元素）：

1. 将序列每相邻两个数字进行归并操作，形成$ceil(\dfrac{n}{2})$个序列，排序后每个序列包含两/一个元素
2. 若此时序列数不是$1$个则将上述序列再次归并，形成$ceil(\dfrac{n}{4})$个序列，每个序列包含四/三个元素
3. 重复步骤$2$，直到所有元素排序完毕，即序列数为$1$

稳定性

因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。

适用场景

归并排序在数据量比较大的时候也有较为出色的表现（效率上），但是，其空间复杂度$\mathcal O(n)$使得在数据量特别大的时候（例如，1千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。

快速排序

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

稳定性

快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。

适用场景

快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。

堆的概念

堆是一种特殊的完全二叉树（complete binary tree）。完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。 如下图，是一个堆和数组的相互关系：

对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标：

• $Parent(i) = floor(\dfrac{i}{2})$，$i$的父节点下标
• $Left(i) = 2i$，$i$的左子节点下标
• $Right(i) = 2i + 1$，$i$的右子节点下标

二叉堆一般分为两种：最大堆和最小堆。 最大堆： 最大堆中的最大元素值出现在根结点（堆顶） 堆中每个父节点的元素值都大于等于其孩子结点（如果存在）

最小堆： 最小堆中的最小元素值出现在根结点（堆顶） 堆中每个父节点的元素值都小于等于其孩子结点（如果存在）

堆排序原理

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

• 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
• 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
• 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算 继续进行下面的讨论前，需要注意的一个问题是：数组都是 Zero-Based，这就意味着我们的堆数据结构模型要发生改变

相应的，几个计算公式也要作出相应调整：

• $Parent(i) = floor(\dfrac{i-1}{2})$，$i$的父节点下标
• $Left(i) = 2i + 1$，$i$的左子节点下标
• $Right(i) = 2(i + 1)$，$i$的右子节点下标

堆的建立和维护

堆可以支持多种操作，但现在我们关心的只有两个问题：

1. 给定一个无序数组，如何建立为堆？
2. 删除堆顶元素后，如何调整数组成为新堆？

先看第二个问题。假定我们已经有一个现成的大根堆。现在我们删除了根元素，但并没有移动别的元素。想想发生了什么：根元素空了，但其它元素还保持着堆的性质。我们可以把​最后一个元素​​（代号A）移动到根元素的位置。如果不是特殊情况，则堆的性质被破坏。但这仅仅是由于A小于其某个子元素。于是，我们可以把A和这个子元素调换位置。如果A大于其所有子元素，则堆调整好了；否则，重复上述过程，A元素在树形结构中不断“下沉”，直到合适的位置，数组重新恢复堆的性质。上述过程一般称为“筛选”，方向显然是自上而下。

删除后的调整，是把最后一个元素放到堆顶，自上而下比较

删除一个元素是如此，插入一个新元素也是如此。不同的是，我们把新元素放在​末尾​，然后和其父节点做比较，即自下而上筛选。

插入是把新元素放在末尾，自下而上比较

那么，第一个问题怎么解决呢？

常规方法是从第一个非叶子结点向下筛选，直到根元素筛选完毕。这个方法叫“筛选法”，需要循环筛选$\dfrac{n}{2}$个元素。

但我们还可以借鉴“插入排序”的思路。我们可以视第一个元素为一个堆，然后不断向其中添加新元素。这个方法叫做“插入法”，需要循环插入$(n-1)$个元素。

由于筛选法和插入法的方式不同，所以，相同的数据，它们建立的堆一般不同。大致了解堆之后，堆排序就是水到渠成的事情了。

算法描述

我们需要一个升序的序列，怎么办呢？我们可以建立一个最小堆，然后每次输出根元素。但是，这个方法需要额外的空间（否则将造成大量的元素移动，其复杂度会飙升到$\mathcal O(n^2)$）。如果我们需要就地排序（即不允许有$\mathcal O(n)$空间复杂度），怎么办？

有办法。我们可以建立最大堆，然后我们倒着输出，在最后一个位置输出最大值，次末位置输出次大值……由于每次输出的最大元素会腾出第一个空间，因此，我们恰好可以放置这样的元素而不需要额外空间。很漂亮的想法，是不是？

稳定性

堆排序存在大量的筛选和移动过程，属于不稳定的排序算法。

适用场景

堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。

希尔排序（插入排序的改良版）

在希尔排序出现之前，计算机界普遍存在“排序算法不可能突破$\mathcal O(n^2)$”的观点。希尔排序是第一个突破$\mathcal O(n^2)$的排序算法，它是简单插入排序的改进版。希尔排序的提出，主要基于以下两点：

1. 插入排序算法在数组基本有序的情况下，可以近似达到$\mathcal O(n)$复杂度，效率极高。
2. 但插入排序每次只能将数据移动一位，在数组较大且基本无序的情况下性能会迅速恶化。

算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列$t_1,t_2,\dots,t_k$，其中$t_i>t_j$，$t_k=1$；
• 按增量序列个数$k$，对序列进行$k$趟排序；
• 每趟排序，根据对应的增量$t_i$，将待排序列分割成若干长度为$m$的子序列，分别对各子表进行直接插入排序。仅增量因子为$1$时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序的增量

希尔排序的增量数列可以任取，需要的唯一条件是最后一个一定为$1$（因为要保证按1有序）。但是，不同的数列选取会对算法的性能造成极大的影响。上面的代码演示了两种增量。 切记：增量序列中每两个元素最好不要出现1以外的公因子！（很显然，按$4$有序的数列再去按$2$排序意义并不大）。 下面是一些常见的增量序列。

• 第一种增量是最初Donald Shell提出的增量，即折半降低直到$1$。据研究，使用希尔增量，其时间复杂度还是$\mathcal O(n^2)$。

第二种增量Hibbard：{$1,3,\dots,2k-1$}。该增量序列的时间复杂度大约是$\mathcal O(n\times 1.5)$。

第三种增量Sedgewick增量：($1,5,19,41,109,\dots$)，其生成序列或者是$9\times 4i- 9\times 2i + 1$或者是$4i - 3\times 2i + 1$。

稳定性

我们都知道插入排序是稳定算法。但是，Shell排序是一个多次插入的过程。在一次插入中我们能确保不移动相同元素的顺序，但在多次的插入中，相同元素完全有可能在不同的插入轮次被移动，最后稳定性被破坏，因此，Shell排序不是一个稳定的算法。

适用场景

Shell排序虽然快，但是毕竟是插入排序，其数量级并没有后起之秀--快速排序O(n㏒n)快。在大量数据面前，Shell排序不是一个好的算法。但是，中小型规模的数据完全可以使用它。

计数排序

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为$i$的元素出现的次数，存入数组$C$的第$i$项；
3. 对所有的计数累加（从$C$中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素$i$放在新数组的第$C(i)$项，每放一个元素就将$C(i)$减去$1$。

稳定性

最后给$b$数组赋值是倒着遍历的，而且放进去一个就将$C$数组对应的值（表示前面有多少元素小于或等于$A_i$）减去一。如果有相同的数$x_1,x_2$，那么相对位置后面那个元素$x_2$放在（比如下标为$4$的位置），相对位置前面那个元素$x_1$下次进循环就会被放在$x_2$前面的位置$3$。从而保证了稳定性。

适用场景

排序目标要能够映射到整数域，其最大值最小值应当容易辨别。例如高中生考试的总分数，显然用$0-750$就OK啦；又比如一群人的年龄，用个$0-150$应该就可以了，再不济就用$0-200$喽。另外，计数排序需要占用大量空间，它比较适用于数据比较集中的情况。

桶排序

1. 找出待排序数组中的最大值$\max$、最小值$\min$
2. 我们使用 动态数组ArrayList作为桶，桶里放的元素也用 ArrayList存储。桶的数量为$\dfrac{\max-\min}{arr.length}+1$
3. 遍历数组$arr$，计算每个元素$arr_i$放的桶
4. 每个桶各自排序
5. 遍历桶数组，把排序好的元素放进输出数组

稳定性

可以看出，在分桶和从桶依次输出的过程是稳定的。但是，由于我们在对每个桶进行排序时使用了其他算法，所以，桶排序的稳定性依赖于这一步。如果我们使用了快排，显然，算法是不稳定的。

适用场景

桶排序可用于最大最小值相差较大的数据情况，但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[$104,150,123,132,20000$], 这种数据会导致前$4$个数都集中到同一个桶中。导致桶排序失效。

基数排序

1. 取得数组中的最大数，并取得位数；
2. $arr$为原始数组，从最低位开始取每个位组成$radix$数组；
3. 对$radix$进行计数排序（利用计数排序适用于小范围数的特点）；

稳定性

通过上面的排序过程，我们可以看到，每一轮映射和收集操作，都保持从左到右的顺序进行，如果出现相同的元素，则保持他们在原始数组中的顺序。可见，基数排序是一种稳定的排序。

适用场景

基数排序要求较高，元素必须是整数，整数时长度$10W$以上，最大值$100W$以下效率较好，但是基数排序比其他排序好在可以适用字符串，或者其他需要根据多个条件进行排序的场景，例如日期，先排序日，再排序月，最后排序年 ，其它排序算法可是做不了的。

总结