十大經典排序算法系列博客——>傳送門

---

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定。桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排）。

總結起來就是一句話：按值劃分成多個區間， 每個區間排序， 最后合并。

算法步驟：

• 設置一個定量的數組當作空桶；

• 遍歷輸入數據，并且把數據一個一個放到對應的桶里去；

• 對每個不是空的桶進行排序；

• 從不是空的桶里把排好序的數據拼接起來。

• 動畫演示：
  

#include <bits/stdc++.h> using namespace std;// 打印數組 void print_array(int *arr, int n) {if(n==0){printf("ERROR: Array length is ZERO\n");return;}printf("%d", arr[0]);for (int i=1; i<n; i++) printf(" %d", arr[i]);printf("\n"); }int* sort_array(int *arr, int n) {int i;int maxValue = arr[0];for (i = 1; i < n; i++) if (arr[i] > maxValue) // 輸入數據的最大值maxValue = arr[i]; // 設置10個桶，依次0，1，，，9const int bucketCnt = 10;vector<int> buckets[bucketCnt];// 桶的大小bucketSize根據數組最大值確定：比如最大值99， 桶大小10// 最大值999，桶大小100// 根據最高位數字映射到相應的桶，映射函數為 arr[i]/bucketSizeint bucketSize = 1;while (maxValue) { //求最大尺寸 maxValue /= 10;bucketSize *= 10;}bucketSize /= 10; //桶的個數 // 入桶for (int i=0; i<n; i++) {int idx = arr[i]/bucketSize; //放入對應的桶 buckets[idx].push_back(arr[i]);// 對該桶使用插入排序(因為數據過少，插入排序即可)，維持該桶的有序性for (int j=int(buckets[idx].size())-1; j>0; j--) {if (buckets[idx][j]<buckets[idx][j-1]) {swap(buckets[idx][j], buckets[idx][j-1]);}}}// 順序訪問桶，得到有序數組for (int i=0, k=0; i<bucketCnt; i++) {for (int j=0; j<int(buckets[i].size()); j++) {arr[k++] = buckets[i][j];}}return arr; }int main() {int n;scanf("%d", &n);int *arr;arr = (int*)malloc(sizeof(int)*n);for (int i=0; i<n; i++) scanf("%d", &arr[i]);arr = sort_array(arr, n);print_array(arr, n);return 0; }

---

若要在桶排序的同時實現對數組的去重， 則用以下代碼（將每個桶的容量看做1）

#include <iostream> #include <algorithm> using namespace std; int main() {int n;bool a[1005]={0};int c;int count=0;cin>>n;for(int i=0;i<n;i++)//輸入數據，存放到數組對應的位置，表示該對應位置有數據了（而且還省了排序）{cin>>c;a[c]=1;}for(int i=0;i<1005;i++)//計算占了位置的數據有多少個，每個桶不管有幾個相同數據，這里之后+1，所以可以說直接去重了{if(a[i]==1)count+=1;}cout<<count<<endl;for(int i=0;i<=1005;i++)//按順序輸出來{if(a[i]==1)cout<<i<<" ";}return 0; }

日拱一卒，功不唐捐。

總結

以上是生活随笔為你收集整理的C++实现桶排序——十大经典排序算法之九【GIF动画+完整代码+详细注释】的全部內容，希望文章能夠幫你解決所遇到的問題。

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