排序算法 互动版

基数排序算法思想

n个记录的关键字进行排序,每个关键字看成是一个d元组:ki=(ki1, ki2,..., kid),其中c0 <=kij <=cr-1 ( 1 <=i <=n, 1 <=j <=d )。

排序时先按kid 的值,从小到大将记录分到r(称为基数)个盒子中,再依次收集;然后按kid-1的值再这样作。直至按ki1分配和收集序列为止,排序结束。

在关键字为数字时,r=10, 0 <=ci <=9, 1 <=i <=d;

在关键字为字母时 r=26, ’A’ <=ci <=’Z’, 1 <=i <=d。


例子一组数:12、 104、 13、 7、 9

*(1)按个位数排序是12、13、104、7、9

*(2)再根据十位排序104、7、9、12、13

*(3)再根据百位排序7、9、12、13、104

如果在某一位的数字相同,那么排序结果要根据上一轮的数组确定,举个例子来说:07和09在十分位都是0,但是上一轮排序的时候09是排在07后面的;同样举一个例子,12和13在十分位都是1,但是由于上一轮12是排在13前面,所以在十分位排序的时候,12也要排在13前面。


基数排序中,r为基数,d为位数。则基数排序的时间复杂度为O(d(n+r))。在基数排序过程中,对于任何位数上的基数进行“装桶”操作时,都需要n+r个临时空间。在基数排序过程中,每次都是将当前位数上相同数值的元素统一“装桶”,并不需要交换位置。所以基数排序是稳定的算法。