算法分析--基数排序
时间复杂度 O（KN）线性
高位优先（不好）
先按照高位升序排序，依次进行下去，直到排到最低位。
image
因为高位有一个分组的动作，在每个组里面对低位再排序。可以用递归。实际上，完全可以用低位排序。
低位排序（好）
image
首先按照个位数字进行一次 稳定排序（相同数字顺序不变）
然后按照十位数字进行一次 稳定排序（相同数字顺序不变）
然后按照百位数字进行一次 稳定排序（相同数字顺序不变）
代码编写
n个数字，如何得到每个数位上的数值：
低位抹去
再取个位（模10）
int index = a[i]/base % 10;
如果想要给每个数字按个位数排序，第一步需要干什么？
找到每个数字应该去的位置的索引。
// 统计每个数字出现的次数
memset(count,0,sizeof(int)*10);
for(int i=0;i<n;i++){
int index = (a[i] / base ) %10; // base是控制当前是个位，十位，还是百位
count[index]++;
}
// 计算每个数字的起始位置
start[0]=0;
for(int i=1;i<10;i++){
start[i]=start[i-1]+count[i-1];
}
// 放入temp临时数组
for(int i=0;i<n;i++){
int index=(a[i] / base )% 10;
temp[start[index]]=a[i];
start[index]++;
}
再思考一个问题：为什么要把temp再拷回去
memcpy(a,temp,n*sizeof(int));
最后一个问题：为什么要计算最大位数（GetMaxDigit）
每个数字的位数可能不一样。比如：3,27,451,98。找出最大位数，就是循环次数。
如果百位是空的，按照代码 3 / 100 = 0 → %10 = 0 就是0，是有效的。
代码总结
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int array[200];
int GetMaxDigit(int n){
int maxdata=*max_element(array,array+n); //max_element是<algorithm>的一个函数,在 [a, a+n) 这个范围里，找到“最大元素的位置,返回指针
int maxdigit = 0;
while(maxdata){
maxdata/=10;
maxdigit++;
}
return maxdigit;
}
void Sort(int n){
int base=1,digit=GetMaxDigit(n);
int temp[n];
int count[10];
int start[10];
while(digit--){
// 统计每个数字出现的次数
memset(count,0,sizeof(int)*10);
for(int i=0;i<n;i++){
int index = array[i]/base%10;
count[index]++;
}
// 计算每个数字的起始位置
memset(start,0,sizeof(int)*10);
for(int i=1;i<10;i++)
start[i]=start[i-1]+count[i-1];
// 放入temp临时数组
memset(temp,0,sizeof(int)*n);
for(int i=0;i<n;i++){
int index = array[i]/base%10;
temp[start[index]]=array[i];
start[index]++;
}
memcpy(array,temp,n*sizeof(int));
base*=10;
}
}
void show(int n){
for(int i=0;i<n;i++){
cout<<array[i]<<" ";
}
}
int main(){
int n;cin>>n; // 有n个数字
for(int i=0;i<n;i++)
cin>>array[i];
Sort(n);
show(n);
return 0;
}