08 基數(shù)排序（Radix Sort）

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

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))???

穩(wěn)定性（相同元素相對位置變化情況）：穩(wěn)定

09 桶排序（Bucket Sort）

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

排序過程：

假設待排序的一組數(shù)統(tǒng)一的分布在一個范圍中，并將這一范圍劃分成幾個子范圍，也就是桶

將待排序的一組數(shù)，分檔規(guī)入這些子桶，并將桶中的數(shù)據(jù)進行排序

將各個桶中的數(shù)據(jù)有序的合并起來

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)? ?

穩(wěn)定性（相同元素相對位置變化情況）：穩(wěn)定

轉載于:https://www.cnblogs.com/wanghao-boke/p/10424469.html

總結

以上是生活随笔為你收集整理的九大经典算法之基数排序、桶排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。