九大經典算法之基數排序、桶排序

08 基數排序（Radix Sort）

基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。排序過程是將所有待比較數值統一為同樣的數位長度，數位較短的數前面補零，然后從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。

int getMax(int arr[], int n) 
{ int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; 
} void countSort(int arr[], int n, int exp) 
{ int output[n]; int i, count[10] = {0}; for (i = 0; i < n; i++) count[ (arr[i]/exp)%10 ]++; for (i = 1; i < 10; i++) count[i] += count[i - 1]; for (i = n - 1; i >= 0; i--) { output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; count[ (arr[i]/exp)%10 ]--; } for (i = 0; i < n; i++) arr[i] = output[i]; 
} void radixsort(int arr[], int n) 
{ int m = getMax(arr, n); for (int exp = 1; m/exp > 0; exp *= 10) countSort(arr, n, exp); 
}

空間效率：O(r)

時間效率：最好情況：O(d(n+r))? ?? ? ? ? ? ? ?平均情況：O(d(n+r))?? ? ? ? ? ? ? ? ? ? ?最壞情況：O(d(n+r))???

穩定性（相同元素相對位置變化情況）：穩定

09 桶排序（Bucket Sort）

桶排序的原理是將數組分到有限數量的桶中，再對每個桶子再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序），最后將各個桶中的數據有序的合并起來。

排序過程：

1. 假設待排序的一組數統一的分布在一個范圍中，并將這一范圍劃分成幾個子范圍，也就是桶
2. 將待排序的一組數，分檔規入這些子桶，并將桶中的數據進行排序
3. 將各個桶中的數據有序的合并起來

void bucketSort(int arr[], int n) 
{ vector<float> b[n]; for (int i=0; i<n; i++) { int bi = n*arr[i]; b[bi].push_back(arr[i]); }   for (int i=0; i<n; i++) sort(b[i].begin(), b[i].end());   int index = 0; for (int i = 0; i < n; i++) for (int j = 0; j < b[i].size(); j++) arr[index++] = b[i][j]; 
}

空間效率：O(N+M)

時間效率：最好情況：O(N)? ?? ? ? ? ? ? ?平均情況：O(N)? ?? ? ? ? ? ? ? ? ? ? ?最壞情況：O(Nlog₂N)? ?

穩定性（相同元素相對位置變化情況）：穩定