算法分析--基数排序

时间复杂度 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;

}