前言：王道书上将排序章节中内部排序分为三小节，其中归并排序，基数排序，计数排序单拎出来作为一小节，另外两节分别是插入排序和交换排序。

一、归并排序

归并利用分治思想，迭代或递归解决问题。

  • 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
  • 解决（Conquer）：用合并排序法对两个子序列递归的排序。
  • 合并（Combine）：合并两个已排序的子序列已得到排序结果

img

平均时间复杂度：O(nlogn)
最佳时间复杂度：O(n)
最差时间复杂度：O(nlogn)
空间复杂度：O(n)
排序方式：In-place
稳定性：稳定

不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )

归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)。

归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。

二、基数排序

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

  • MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
  • LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

对于LSD：

① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。

② 从最低位开始，依次进行一次排序。

③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

img

对于基数排序的复杂度：

时间复杂度：O(k*N)
空间复杂度：O(k + N)
稳定性：稳定

三、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序。

计数排序要求输入的数据必须是有确定范围的整数。

动图

计数排序的复杂度：

  • 平均时间复杂度：O(n + k)
  • 最佳时间复杂度：O(n + k)
  • 最差时间复杂度：O(n + k)
  • 空间复杂度：O(n + k)

补充桶排序：

与计数排序有类似之处。设置多个有序的桶，将要排序序列中的值，放置到这些桶里。对每个桶内的数据使用快速排序算法进行排序，最后按照桶的顺序将每个桶的数据依次取出并合并。

img