聊聊非比较排序

计数排序

计数排序，其实就是利用范围为最小值~最大值的辅助数组进行排序，排序流程如下：

流程

假设输入为1-10之间的数组，输入元素为a（7,2,4,6,8），计数器为b

1. 遍历输入元素，统计每个计数辅助数组的数量。

   // 计算每个计数器的元素数量
   1 2 3 4 5 6 7 8 9 10
   0 1 0 1 0 1 1 1 0 0

2. 每个计数器后一个元素加等于上一个元素，用来设置顺序。

   // 累计之后的结果
   1 2 3 4 5 6 7 8 9 10
   0 1 1 2 2 3 4 5 5 5 

3. 倒序（为了保证稳定性）遍历输入元素，按照对应的顺序设置数组（交换元素或者设置到新数组）

   // 假设设置到新数组c
   c[b[a[5]]-1] = a[5];
   c[b[a[4]]-1] = a[4];
   // ...

基数排序

基数排序其实就是对每个位进行计数排序之后的结果，可以用于数量级比较大的数字。

流程

假设位为10，输入的数组为：324，45,273。

1. 获取最大值为位数，如324为3位。

2. 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），这里假设使用LSD从最右边开始，依次对每位进行计数排序。

   // 第一轮
   2 7 [3]
   3 2 [4]
   0 4 [5]
   // 第二轮
   3 [2] 4
   0 [4] 5
   2 [7] 3
   // 第三轮
   [0] 4 5
   [2] 7 3
   [3] 2 4

桶排序

假设输入数字范围为0-50，可以分成5个桶：0-9，10-19，20-29，30-39，40-49。桶排序动画参考

流程

1. 输入元素分配到对应的桶，在入桶的时候，可以对桶内元素进行插入排序。
2. 将所有桶中的数据有序合并起来。