数据结构之排序算法：基数排序

思维导图&＃xff1a;

基数排序的定义&＃xff1a;

ps&＃xff1a;
n表示线性表长度
d表示每个元素的位数&＃xff0c;例324有三位数字
r表示基数&＃xff0c;10进制基数是10&＃xff0c;2进制基数是2

分配和收集&＃xff1a;

例&＃xff1a;低位优先
第一次分配收集&＃xff1a; 以个位为准

按Q~0~到Q~9~的顺序收集&＃xff0c;结果为第一次分配收集结果


第二次分配收集&＃xff1a; 以十位为准
按Q₀到Q₉的顺序收集&＃xff0c;结果为第二次分配收集结果

第三次分配收集&＃xff1a; 以百位为准
按Q₀到Q₉的顺序收集&＃xff0c;结果为第三次分配收集结果

基数排序的性能&＃xff1a;

时间复杂度&＃xff1a; O(d*(n&＃43;r))
空间复杂度&＃xff1a; O( r )
稳定

基数排序应用&＃xff1a;