数据结构几大排序算法总结（实现、复杂度）
简介
排序在数据结构中的内部排序部分，主要介绍了几大常见的排序算法，这里做一下简单的分析总结。
排序： 按关键字大小顺序排列数据。
时间复杂度： 简单的排序方法 O(
n
2
n^2
n2)，先进的排序方法 O(nlogn)
排序方法的稳定性： 稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序。
冒泡排序，
规则：“依次比较相邻元素，‘逆序’则交换。
冒泡排序(52， 49， 80， 36， 14， 58， 61)。
下面是第一趟排序后的结果，确定了最大值80。
由于两个相同元素比较时如（49,49）由于两值相同，不做交换，故冒泡排序是稳定的。时间复杂度 O(
n
2
n^2
n2)
快速排序
快速排序可以看我的另一篇文章讲的很详细快速排序（详解及python实现）
时间复杂度：平均情况下，时间复杂度 O(nlogn)。 记录本来有序时为最坏情况，时间复杂度为 O(n2)。
空间复杂度：(考虑递归调用的最大深度)在平均情况下为 O(logn)，在最坏情况下为O(n)。
简单选择排序
规则： 第 i 趟排序过程是在剩余的待排记录中选一个最小（大）的，放在第 i 个位置。即“在待排记录中选取最小的，交换到合适位置，重复n-1 次”
例： {52 49 80 36 14 58 61}简单选择排序。
第一趟遍历，找到最小值14，放在第一个位置（与52交换）
第二趟遍历，固定第一个位置值14不再参与遍历，找到最小值36，放在第一个位置（与49交换）
第三趟遍历，固定前两个位置值14、36不再参与遍历，找到最小值49，放在第一个位置（与80交换）
以此类推，直到剩下最后一个元素，排序完成：
选择排序是不稳定的：
如（
5
1
5_1
51 ，
8
8
8，
5
2
5_2
52，
2
2
2，
9
9
9 ）–> （
2
2
2，
8
8
8，
5
2
5_2
52，
5
1
5_1
51 ，
9
9
9）
时间复杂度 O(n2)，耗费在比较记录上，比较次数始终为 n(n-1)/2，
堆排序
堆： 用数组实现的二叉树（一种非线性结构）,所以它没有使用父指针或者子指针
小顶堆： 每个结点的值都大于或等于其左右孩子结点的值
大顶堆： 每个结点的值都小于或等于其左右孩子结点的值
例：把(24,85,47,53,30,91,12,36)调整成小顶堆。
堆和普通树的区别：
内存： 普通树要为节点对象以及左/右子节点指针分配额外的内存。堆仅仅使用数组且不使用指针。
平衡：
二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(nlog2n)。可以按任意顺序位置插入/删除数据。
堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(nlog2n) 的性能。
搜索：
二叉树中搜索会很快。堆中搜索会很慢，在使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。
规则： 对于一个无序序列如何进行堆排序？
- 先建立大顶堆
- 然后交换堆顶与最后一个元素
- 对剩下的序列继续建立大顶堆，重复以上操作，直到剩下最后一个元素
例： (24,85,47,53,30,91,12,36)进行堆排序。
堆排序是不稳定的。时间复杂度是 O(nlogn)。
归并排序
规则： 两个或多个有序表合并成一个有序表。
例：对{24, 85, 47, 53, 30, 91}归并排序。
时间复杂度 O(nlogn)。空间复杂度 O(n)。归并排序是稳定的排序。
插入排序
1 直接插入排序
将待排序记录插入已排好的记录中，不断扩大有序序列，即“将待排序记录插入有序序列，重复n-1 次”。
以第一个元素不动，对后面的元素一一进行插入。再对后面的序列重复以上操作，直到所有元素插完。
例： 52， 49， 80， 36， 14， 58， 61 进行直接插入排序。
算法的时间复杂度 O(
n
2
n^2
n2)。直接插入排序是稳定的排序算法。
2 希尔排序（缩小增量排序）
规则： 先将待排序列分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进行直接插入排序。
步骤：
- 分成子序列(按照增量 dk)；
- 对子序列排序(直接插入排序)；
- 缩小增量，重复以上步骤，直到增量 dk=1。4.
增量，即从 gap=length/2 逐步减半，增量序列中最后一个增量一定是 1，如： … 9, 5, 3, 2, 1 和… 13, 4, 1。如没有明确说明增量序列可以选择… 3, 2, 1 或… 5, 3, 2, 1。
例：希尔排序(52， 49， 80， 36， 14， 58， 61)。
希尔排序是不稳定的。时间复杂度大约为 O(n3/2)。
3 折半插入排序
规则： 在直接插入排序中，查找插入位置时采用折半查找的方法。
时间复杂度 O(
n
2
n^2
n2)。比直接插入排序减少了比较次数。折半插入排序是稳定的排序算
法。
总结
| 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 冒泡排序 | n 2 n^2 n2 | 1 1 1 | 稳定 |
| 快速排序 | n l o g n nlogn nlogn | n l o g n nlogn nlogn | 不稳定 |
| 简单选择排序 | n 2 n^2 n2 | 1 1 1 | 不稳定 |
| 堆排序 | n l o g n nlogn nlogn | 1 1 1 | 不稳定 |
| 归并排序 | n l o g n nlogn nlogn | 1 1 1 | 稳定 |
| 直接插入排序 | n 2 n^2 n2 | 1 1 1 | 稳定 |
| 希尔排序 | n 3 / 2 n^{3/2} n3/2 | 1 1 1 | 不稳定 |
| 折半插入排序 | n 2 n^2 n2 | 1 1 1 | 稳定 |