什么是排序算法稳定性？

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的。

常见排序算法介绍

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

具体实现算法（python）如下图:

时间复杂度：平均 O(n^2) 最优 O(n) 最差 O(n^2)

空间复杂度：O(1)

是否稳定性算法：是

选择排序

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

具体实现算法（python）如下图：

时间复杂度：平均 O(n^2) 最优 O(n^2) 最差 O(n^2)

空间复杂度：O(1)

是否稳定排序算法：是（在判断用>=时，非稳定）

冒泡排序

重复走访要排序的序列，两两比较顺序错误就交换，依此类推，直到走完要排序序列，这时最大（最小）数浮动到数列末尾。

具体算法实现（python）如下图：

时间复杂度：平均 O(n^2) 最优 O(n^2) 最差 O(n^2)

空间复杂度：O(1)

是否稳定排序算法：是

快速排序

又称划分交换排序。快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）。

分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成。

递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

具体算法实现（python）如下图：

时间复杂度：平均 O(nlogn) 最优 O(nlogn) 最差O(n^2)

空间复杂度：O(logn) - 递归堆栈

是否稳定排序算法：否 （如：[ 4, 2, 3, 2] -> [2, 2, 3, 4]）这里的 4 - 2 交换，导致原有的 2、2排序被打乱。

堆排序

新建堆然后从堆中逐条取出元素。

具体算法实现（python）如下图：

时间复杂度：平均 O(nlogn) 最优 O(nlogn) 最差 O(nlogn)

空间复杂度：O(logn) - 递归堆栈

是否稳定排序算法：否

其它

完全二叉树：完全二叉树的根节点到倒数第二层节点满足完美二叉树，最后一层节点可以不完全填充，但满足靠左对齐。

堆：一种树状数据结构，需要满足如下性质：

1. 堆中的某个节点的值总是大于等于或小于等于其父节点的值；

2. 堆总是一颗完全二叉树；

归并排序

建立在归并操作基础上的一种有效排序方式，采用分治法：

1、分割：递归地把当前序列平均分割成两半。

2、集成：将上一步得到的有序子序列集成到一起（归并）。

具体算法实现（python）如下图：

时间复杂度：平均 O(nlogn) 最优 O(nlogn) 最差 O(nlogn)

空间复杂度：O(logn)

是否稳定性算法: 是

其它

归并操作：将两个有序集合合并成一个有序集合。

希尔排序

也称递减增量排序算法，是插入排序的一种更高效的改进版本。它是基于插入排序的一下两点性质改进点：

1、插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

2、插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

即通过指定步长排序，使得原有序列变得尽可能有序，从而使得最后一步的插入排序的效率极大提升，从而使得总排序时间高效。

具体算法实现（python，这里使用的递归 n/2 的步长）如下图：

时间复杂度：平均 O(nlogn) 最差 O(n^2)

空间复杂度：O(1)

是否稳定算法：是(上述代码实现是，有些版本可能不是)

实现代码：

https://github.com/zdxu/data-structure-and-algorithm/tree/master/sort_algorithm