算法分析--基数排序

基数排序简介

• 只讨论非负整数
  
• 认为个位，十位分别是一个关键字
  
• 时间复杂度 O（KN）线性
  

高位优先（不好）

先按照高位升序排序，依次进行下去，直到排到最低位。

出自https://juejin.cn/post/6998015030247718942
因为高位有一个分组的动作，在每个组里面对低位再排序。可以用递归。实际上，完全可以用低位排序。
低位排序（好）

• 首先按照个位数字进行一次 稳定排序（相同数字顺序不变）
  
• 然后按照十位数字进行一次 稳定排序（相同数字顺序不变）
  
• 然后按照百位数字进行一次 稳定排序（相同数字顺序不变）
  

代码编写

n个数字，如何得到每个数位上的数值：

• 低位抹去
  
• 再取个位（模10）
  

1. int index = a[i]/base % 10;

复制代码

如果想要给每个数字按个位数排序，第一步需要干什么？

• 找到每个数字应该去的位置的索引。
  

[code]// 统计每个数字出现的次数memset(count,0,sizeof(int)*10);for(int i=0;i