数据结构和算法分析-排序总结（含图解）
概述
稳定性
排序算法稳定，是指能保证排序前2个相等的数在序列的前后位置顺序和排序后他们两个的前后位置顺序相同。即：a=b,排序前a在b之前，排序后a还应该在b之前。
稳定性：冒泡，插入，归并
时间
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 | 操作 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | 俩俩比较，大的放后面*N，直到没有移动的需要（数组后面会慢慢形成有序区） |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | 找到无序区最小（大），放到有序区末尾。 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | 从无序区取数，排到有序区，重复 |
| 希尔排序 | O(n*log(n))~O(n^2) | O(n^1.3) | O(n^1.5) | O(1) | 不稳定 | 分成k组，分别插入排序，k减小，重复 |
| 堆排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(1) | 不稳定 | 二叉堆，deleteMin*N |
| 归并排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(n) | 稳定 | 均分N组，组合排好序的组*N |
| 快速排序 | O(n*log(n)) | O(n*log(n)) | O(n^2) | O(1) | 不稳定 | 两侧开始往中间，（左边遇到大雨基准的，右边遇到小于基准时，交换）*N |
总结时间：
O(n^2):冒泡、选择、插入
O(n log n)：堆、快速、归并
O(n log^2 n)：希尔、归并
冒泡排序
图解
冒泡排序算法的运作如下：（从后往前）
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
插入排序
图解
结构：
插入排序由N—1趟排序组成，对于P=1到N - 1,插入排序保证了从位置0到 p-1的位置已处于排序状态
第P趟我们将位置P上的元素向左移动，知道它在前P+1个元素中找到正确的位置
时间：
O（N2）；由于嵌套循环的每一次都要执行N此迭代，因此插入排序为O（N2），每次以反序的输入可以达到该界，如果数据已经排序那么运行时间为0（N）
实现：
从第一个值开始遍历，存储当前遍历到的p上的值，向前遍历，每次把遍历到的值往后放一个位置，直到这个值>p。
希尔排序
插入排序的一种
它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到比较相邻两项为止。
由于这个原因，希尔排序有时也叫作缩减增量排序
图解：
结构：
在使用增量hk排序后，对于每一个i我们都有a[i] <= a[i+k]此时所有想个K的元素都被排序了，此时称为文件的hk排序
不断把hk缩小，最终达到排序成功
也可以看作是把序列每次分成多组分别排序,a[i]／a[i+k]／a[i+2k]／a[i+3k]等等分为一组排序
时间：
最坏情景运算时间为O（N2）
使用Hibbard增量的希尔排序最坏时间复杂度为O（N3/2）
Hibbard 增量 形如 1，3，7, ….,2K-1
实现：
和插入排序一致，外面再嵌套一个for循环，不断减少hk。
堆排序
图解
结构：
建立N个元素的二叉堆的，执行N次deleteMin操作，按照规则最小的元素先离开堆，堆缩小1，把最小的元素放在被删除的堆最后的单元
时间：
最坏运行时间O（N log N）
实现：
优先队列可以使用O（N log N）的时间排序，基本思想的算法叫做堆排序，他给出我们至今所见到的最佳的大O运行时间
1.建立N个元素的二叉堆的，这个阶段花费O（N）时间，最多用到2N次比较
2.然后我们执行N此deleteMin操作，按照规则最小的元素先离开队列，通过把这些元素记录在第二个数组 这阶段花费O（log N） 最多用到2N logN -O(N)次比较、
因此总运行时间为O（N log N） 最多用到2N logN -O(N)次比较、
该算法需要多增加一倍的空间
归并排序
图解：
结构：
该算法的基本操作时合并两个已排序的表，因为两个表是已排序的，所以将输出放到第三个表中。
时间：
O(Nlog N)最坏时间，使用的比较次数是最优的
实现：
则该算法可以通过对输入数据一趟排序来完成。基本的合并算法是去两个输入数组A和B，一个输入数组C，以及3个计数器
快速排序
图解
结构：
如果表中含有大量的重复项，以及相对较少的不同项，其表现还是不错的
应该避免建立第二组（包含等于项的）
时间：
时间复杂度：O（n*lgn）
最坏：O（n^2）
空间复杂度：O（n*lgn）
不稳定。
通常是用于排序的最佳选择。因为，基于比较的排序，最快也只能达到O（nlgn）。
实现：
枢纽元取出放在数组最右边，两个指针分别从数组最左边和最右边第二个开始相近移动
左边数字大于枢纽元，右边数字小于枢纽元时停止，两个指针均停止时，交换数字
直到指针交错，交换左指针和枢纽元
7.7.3 小数组
对于很小的数组，快速排序不如插入排序（N < 20）
7.7.6选择问题的线性期望时间算法
快速选择：
1、令|Si|为Si中元素的个数
2、选取一个枢纽元v属于S
3、将集合S-{v}分割成S1和S2，就像我们在快速排序中所作的那样
4、如果k<=|S1|，那么第k个最小元素必然在S1中。在这种情况下，返回quickselect（S1,k）。如果k=1+|S1|，那么枢纽元素就是第k个最小元素，即找到，直接返回它。否则，这第k个最小元素就在S2中，即S2中的第（k-|S1|-1）个最小元素，我们递归调用并返回quickselect（S2，k-|S1|-1）
排序算法的一般下届
虽然我们得到了一些O（Nlog N）的排序算法，但是，尚不清楚我们是否还能做更好。我们证明，任何只用到比较排序算法的最坏情况都需要Ω（N log N）此比较，因此归并排序和堆排序在一个常数因子范围内都是最优秀的。这也意味着快速排序在相差一个常数因子的时候时最优秀的
只用到比较的任何排序算法在最坏情况下都需要（log(N!)）此比较
决策树
证明下界的抽象概念，每个节点表示在元素之间一组可能的排序。
选择问题的决策树下届
任意基于比较排序算法都必须用到大约N log N此比较，
跳过一部分
线性时间的排序 桶排序和基数排序
桶排序 ： 使用大小为M（元素小于M）的称为count的数组，初始化全部为0于是count有了M个单元（或称为桶），初始化为空，当读入Ai时count增加一，在所有内容都别输入后，扫描数组。该算法的用时O（M+N）,如果M为O(N),那么总用时就是O（N）
适用于一些小整数的情况
基数排序： 一般的 对某常数考虑值域从0 ~ bp 的数字，显然不能使用桶排序，窍门是使用多次桶排序。
自然的算法是对最高位的数字用桶排序，再对此高位排序。。。。
但是此时桶的数量会过多，因为比较完毕高位，每个高位的低位也需要相同数量的桶。
更简单的是从最低位开始：
1、先根据低位数字比较放入1桶中
2、比较次低位，先拿小的桶中的数字放入2桶中，此时每个桶中有相对顺序存在
3、比较高一位，先拿小的桶中的数字放入3桶中，此时每个桶中有相对顺序存在……..全部比较完毕，桶中的顺序也排好了。
计数基数排序：
外部排序
迄今为止我们考察的算法都是输入数据装入内存，然而存在一些应用，他们输入的数据量太大了，装不进内存。本节将谈论这些外部排序算法，他们是设计来处理很大的数据的
如果数据在硬盘上，由于磁盘转动和移动磁头所需要的时间，会使效率损失
7.12.3 简单算法
基本的外部排序算法使用归并排序中的合并算法
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的
小结
对于大部分一般的内部排序的运用都是 插入排序，希尔排序，归并排序就是快速排序，这主要是底层环境来决定的。
插入排序使用于非常少量是输入
对于中等附魔的输入 希尔排序是一个不错的选择，它可以用少了代码就能给出优异的表现
归并排序在最坏情况下变现O（logN），但需要额外的空间然而，它用到的比较次数几乎是最优的