小白必学排序算法（八）---基数排序

基数排序，是一种很特殊的排序方法。采用多关键字排序思想（即基于关键字的大小进行排序的），借助"分配"和"收集"两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先(MSD)排序和最低位(LSD）排序。

它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。 具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序图文说明：

(1)遍历序列找出最大的数(为的是确定最大的数是几位数)；



(2)开辟一个与数组大小相同的临时数组tmp；



(3)用一个count数组统计原数组中某一位(从低位向高位统计)相同的数据出现的次数；



(4)用一个start数组计算原数组中某一位(从最低位向最高位计算)相同数据出现的位置；



(5)将桶中数据从小到大用tmp数组收集起来；



(6)重复(3)(4)(5)直到所有位都被统计并计算过，用tmp收集起来；



(7)将tmp数组拷回到原数组中；

通过基数排序对数组

{123，234，564，765，876，324，651，874，432}，

它的示意图如下：

在这里插入图片描述

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