八大排序算法
各种排序算法比较(2):时间复杂度,空间复杂度
数据结构与算法系列 目录
排序算法中用到的几个概念：
- 排序算法稳定性：假定在待排序的记录序列中，存在多个相同的关键字，如果经过排序之后，这些计算的相对次序保持不变，既在原序列中
r[i] = r[j]，且r[i]在r[j]之前，排完序之后，r[i]仍在r[j]之前，那么就称这种算法是稳定的。
将一个记录插入已经排好的有序表中，得到一个新的有序比。先将序列的第一个元素看成是有序的子序列，然后从第 2 个记录逐个进行插入，直到整个序列有序。一般认为插入排序是稳定的。
排序算法时间复杂度是 O(n2)，最优情况是 O(n)，该种情况下初始的序列已经排好序了。空间复杂度是 O(1)。
希尔排序是对直接插入排序的改进。基本思想是：对于长度为 n 的待排序序列，首先取一个小于 n 的整数 d（d 又被称为步长或者增量），序列中元素距离为 d 的倍数的元素放在同一个组中，这样将可以将整个序列分为 d 组，分别对这 d 组元素进行排序，排完序后每组中的元素都是有序的。逐渐减小 gap 的值，重复上面的分组和排序过程。当 d = 1 的时候，整个序列就是有序的了。
希尔排序的复杂度和 d 的选取有关，当 d = 1 时，算法就退化为直接插入排序，此时复杂度为 O(n2)。其他步长的复杂度可能是 O(n3/2) 或者 O(n4/3) 或者 O(n lg2(n))
在要排序的一组数中，选出最小值（最大值）与第一个位置的元素交换，然后在剩下的数种再最小值（最大值）与第二个位置交换，依次类推，直到第 n - 1 个元素和第 n 个元素比较为止。
选择排序的时间复杂度是 O(n2)，空间复杂度为O(1)。直接选择排序是稳定的。
堆排序是一种树形排序方式。这里排序使用二叉堆，即只有两个孩子节点。二叉堆其实就是一颗二叉树，该树满足以下性质：
- 堆中任意节点的值总是不大于（不小于）其子节点的值
- 堆总是一颗完全二叉树
- 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边
以最小堆为例，对于要排序的 n 个数，首先将其整理成一个最小堆，删除根节点并将根节点输出，然后将剩余的节点重新整理成最小堆，再删除根节点，重复这个过程，就可以获得一个排好序的递增序列。对于堆排序需要解决两个问题：
- 如何将初始元素构建成堆
- 删除元素后如何调整剩余的元素，使其成为一个最大堆
对于第一个问题，就相同于向一个空的堆里插入 n 个元素，过程如下：
- 将新插入的元素放入堆的末尾，如果堆为空，该元素就作为根节点，插入完成
- 将新插入的元素与其父节点比较，如果大于父节点，那么插入完成，如果小于父节点，就将父节点和新节点进行交换
- 将交换后的新节点和它现在的父节点比较，重复 2 的过程，直到新节点大于其父节点或者新节点成为根节点。
对于第二个问题，过程如下：
- 删除根节点，将堆底的元素放到根节点上
- 如果根节点大于其子节点，即不满足堆性质，将根节点和左右子节点中较小的元素进行交换
- 继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。
堆排序的时间复杂度为 O(nlogn)，空间复杂度是 O(1)。堆排序不是稳定的。
将两个有序数列合并成一个有序数列的操作称为归并。归并排序 （Merge sort）是建立在归并操作上的一种排序算法。根据具体的实现，归并排序包括 从上到下 和 从下往上 两种方式：
- 从下往上： 将待排序的数列分为若干个长度为 1 的有序子数列，然后两两合并，获得若干长度为 2 的有序子数列，然后将长度为 2 的有序子数列合并成长度为 4 的有序子数列，依此类推，直到整个数列都有序。
- 从上往下： 从上往下比从下往上多了一个分解步骤，基本步骤如下：
- 分解 -- 将当前区间一分为二，分裂点为
mid = (low + high) / 2，递归地对两个子区间a[low ... mid]和a[mid+1 ... high]进行分解，直到两个区间的大小变为 1. - 归并 -- 将两个有序的子区间进行合并成一个有序区间
- 分解 -- 将当前区间一分为二，分裂点为
下面是图示：
归并排序的时间复杂度是 O(nlog(n))，空间复杂度是 O(n)，归并排序是稳定的。