最近又有個奇奇怪怪的題目，資料為 \(n \le 1 \times 10^7\)，并且還要用到排序，普通的排序肯定會超時，然后就發現了一種 \(O(n)\)
介紹
基數排序(Radix Sort)是桶排序的擴展，它是將整數按位數切割成不同的數字，然后按每個數位分別比較以此來排序，
說詳細點，也就是將所有數字統一為同樣的長度，數位較短的數前面補零，然后，從最低位開始，依次進行一次排序，然后從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列，
下面就用表格來做個詳細的解釋：
| 最開始的序列 |
|---|
| 214 |
| 135 |
| 413 |
| 435 |
| 533 |
| 345 |
| 532 |
| 421 |
| 654 |
| 431 |
既然從小到大排序，那么先排個位，
| 排完個位后 |
|---|
| 421 |
| 431 |
| 532 |
| 413 |
| 533 |
| 214 |
| 654 |
| 135 |
| 435 |
| 345 |
再排十位
| 排完十位后 |
|---|
| 413 |
| 214 |
| 421 |
| 431 |
| 532 |
| 533 |
| 135 |
| 435 |
| 345 |
| 654 |
最后再排百位
| 排完百位后 |
|---|
| 135 |
| 214 |
| 345 |
| 413 |
| 421 |
| 431 |
| 435 |
| 532 |
| 533 |
| 654 |
這便是最后的序列，
程序
1.查找陣列a的最大值，并求出最大值的位數，作為回圈的次數
2.統計所有數字某一位，用個桶 \(ct\) 來記個數，
3.然后做個前綴和ct[i]+=ct[i-1]，那么每個數的某一位 \(x\) 的排名就應該在 \(ct[x-1]+1 \sim ct[x]\)，
4.然后按照上一次排序的結果，利用 \(ct\) 逐一放進另一個陣列，再賦值到原來陣列上，
5.重復進行（2）（3）（4）的操作，
代碼
int maxbit(int a[],int n){
int maxx=0;
for(int i=1;i<=n;i++){
int s=0,p=a[i];
while(p!=0){
p=p/10;
s++;
}
maxx=max(maxx,s);
}
return maxx;
}
void Radix_Sort(int a[],int n){
int m=maxbit(a,n),g=1;
for(int t=0;t<=m;t++){
for(int i=0;i<=9;i++)
ct[i]=0;
for(int i=1;i<=n;i++){
int p=(a[i]/g)%10;
ct[p]++;
}
for(int i=1;i<=9;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--){
int p=(a[i]/g)%10;
rak[ct[p]]=a[i];
ct[p]--;
}
for(int i=1;i<=n;i++){
a[i]=rak[i];
}
g=g*10;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/556685.html
標籤：其他
上一篇：基數排序
下一篇：返回列表