算法分析–基数排序

基数排序简介

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

高位优先（不好）

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

出自https://juejin.cn/post/6998015030247718942

因为高位有一个分组的动作，在每个组里面对低位再排序。可以用递归。实际上，完全可以用低位排序。

低位排序（好）

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

代码编写

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; }