基数排序,是一种很特殊的排序方法。采用多关键字排序思想(即基于关键字的大小进行排序的),借助"分配"和"收集"两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先(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) 稳定性:稳定