/ 算法  

了解你使用的 Sort ( 实现剖析) - 3

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

往期:

归并排序

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

思路:

  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的值 ↓