先上图， 本篇文章涉及 归并排序 和 基数排序 两种算法

往期：

归并排序

归并排序使用分治法，核心在于数列的“分”与“合”，不断地将两个已排好序的数组合并一个有序数组

思路：

  1. 将数组分割为两个部分，创建新的数组a1和 b1
  2. 如果a1的长度大于2，则继续执行1过程，直至ai
  3. 将ai中两个数字进行比较交换位置形成有效数组
  4. 递归向上比较两个数组大小并合并成新的有序数组 (例如比较数组第一位，即可得出哪个数组更小)

 

参考动画去理解 ↓

基数排序

前置条件：

  • 必须为整数数组，或者你可以转化为整数数组
  • 知道数组的位数范围（比如 0 - 999 最多三位）

基数排序是桶排序的改进算法。由于桶排序需要创建数组数据范围长度的空间，很浪费空间，基数排序则是一个逐位(个位、十位、百位等)的桶排序，空间仅需长度为10的数组

思路：

  1. 首先只关注数组a中每个数的个位
  2. 创建数组b长度为10 值默认0，遍历数组a，关注个位，如果值位9，则b[9]的值加1。即b[a[i]]++，最终得到个位数0-9分别有几个
  3. 再次遍历数组a，进行基于个位的排序。由于步骤2可以确认每个数值的排序后索引范围，比如b[0]长度为3的话，所有a中个位为0的只要放在0-3位即可
  4. 对十位再次进行上述步骤，逐位数进行排序

 

参考动画去理解 （有点长 四分钟）↓

 

这个动画可能更好理解点，差别是这次的数组b是个二维数组，直接存入数组a的值 ↓