在前幾回我們已經對 、 、 、 、 、 、 、 、 做了說明分析。本回,將對基數排序 進行相關說明分析。
一、排序算法系列目錄說明
二、基數排序(RadixSort)
基數排序(Radix sort)是一種非比較型整數排序算法。
1. 基本思想
原理是將整數按位數切割成不同的數字,然後按每個位數分別比較。基數排序的方式可以採用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由鍵值的最右邊開始,而MSD則相反,由鍵值的最左邊開始。
MSD:先從高位開始進行排序,在每個關鍵字上,可採用計數排序
LSD:先從低位開始進行排序,在每個關鍵字上,可採用桶排序
2. 實現邏輯
① 將所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零。
② 從最低位開始,依次進行一次排序。
③ 這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。
3. 動圖演示
分步圖示說明:設有數組 array = {53, 3, 542, 748, 14, 214, 154, 63, 616},對其進行基數排序:
在上圖中,首先將所有待比較數字統一為統一位數長度,接著從最低位開始,依次進行排序。
按照個位數進行排序。
按照十位數進行排序。
按照百位數進行排序。
排序後,數列就變成了一個有序序列。
4. 複雜度分析
時間複雜度:O(k*N)
空間複雜度:O(k + N)
穩定性:穩定
設待排序的數組R[1…n],數組中最大的數是d位數,基數為r(如基數為10,即10進制,最大有10種可能,即最多需要10個桶來映射數組元素)。
處理一位數,需要將數組元素映射到r個桶中,映射完成後還需要收集,相當於遍歷數組一遍,最多元素數為n,則時間複雜度為O(n+r)。所以,總的時間複雜度為O(d*(n+r))。
基數排序過程中,用到一個計數器數組,長度為r,還用到一個rn的二位數組來做為桶,所以空間複雜度為O(rn)。
基數排序基於分別排序,分別收集,所以是穩定的。
5. 代碼實現
<code>int maxbit(int data[], int n) //輔助函數,求數據的最大位數
{
int maxData = data[0];\t\t///< 最大數
/// 先求出最大數,再求其位數,這樣有原先依次每個數判斷其位數,稍微優化點。
for (int i = 1; i < n; ++i)
{
if (maxData < data[i])
maxData = data[i];
}
int d = 1;
int p = 10;
while (maxData >= p)
{
//p *= 10; // Maybe overflow
maxData /= 10;
++d;
}
return d;
/* int d = 1; //保存最大的位數
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
p *= 10;
++d;
}
}
return d;*/
}
void radixsort(int data[], int n) //基數排序
{
int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int[10]; //計數器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //進行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空計數器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //統計每個桶中的記錄數
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶
for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) //將臨時數組的內容複製到data中
data[j] = tmp[j];
radix = radix * 10;
}
delete []tmp;
delete []count;
}/<code>
三、總結
基數排序與計數排序、桶排序這三種排序算法都利用了桶的概念,但對桶的使用方法上有明顯差異:
基數排序:根據鍵值的每位數字來分配桶;
計數排序 :每個桶只存儲單一鍵值;
桶排序:每個桶存儲一定範圍的數值;
基數排序不是直接根據元素整體的大小進行元素比較,而是將原始列表元素分成多個部分,對每一部分按一定的規則進行排序,進而形成最終的有序列表。
PS: 更多精選內容資源分享,歡迎關注微信公眾號:『 developer1024 』
閱讀更多 休閒遊戲人 的文章