原創(chuàng)不易，轉(zhuǎn)載請注明出處。歡迎點贊收藏~

桶排序（Bucket Sort）是一種排序算法，它將待排序的數(shù)據(jù)分到幾個有序的桶中，每個桶再分別進(jìn)行排序，最后將各個桶中的數(shù)據(jù)按照順序依次取出，即可得到有序序列。

具體步驟如下：

1. 首先確定桶的個數(shù)和每個桶的取值范圍。通常會根據(jù)輸入數(shù)據(jù)的特點來確定桶的個數(shù)，例如數(shù)據(jù)的分布情況、數(shù)據(jù)量等。
2. 將待排序的數(shù)據(jù)依次放入對應(yīng)的桶中?？梢允褂糜成浜瘮?shù)將待排序數(shù)據(jù)映射到桶中，或者直接使用數(shù)據(jù)本身作為桶的索引。
3. 對每個非空的桶進(jìn)行排序?？梢允褂貌迦肱判?、快速排序、歸并排序等排序算法對每個桶中的數(shù)據(jù)進(jìn)行排序。
4. 將各個桶中的數(shù)據(jù)按照順序依次取出，即可得到有序序列。

桶排序的時間復(fù)雜度取決于對每個桶內(nèi)部數(shù)據(jù)進(jìn)行排序的時間復(fù)雜度。假設(shè)有n個元素，將它們均勻地分到m個桶中，那么每個桶中平均有n/m個元素。如果對每個桶采用快速排序等線性時間復(fù)雜度的排序算法，則桶排序的時間復(fù)雜度為O(n+m)，其中n為待排序數(shù)據(jù)的個數(shù)，m為桶的個數(shù)。如果n和m接近相等，則時間復(fù)雜度近似為O(n)。

桶排序的空間復(fù)雜度取決于桶的個數(shù)和每個桶中數(shù)據(jù)的個數(shù)。通常情況下，桶排序的空間復(fù)雜度為O(n+m)，其中n為待排序數(shù)據(jù)的個數(shù)，m為桶的個數(shù)。如果n和m接近相等，則空間復(fù)雜度近似為O(n)。

需要注意的是，桶排序適合用于待排序數(shù)據(jù)分布比較均勻的情況，如果數(shù)據(jù)分布不均勻，可能會導(dǎo)致某些桶中的數(shù)據(jù)量過大，從而影響排序效果。

以下是一個使用C語言實現(xiàn)的桶排序示例：

#include <stdio.h>// 桶排序函數(shù)
void bucket_sort(int arr[], int n, int max)
{// 創(chuàng)建桶數(shù)組int buckets[max + 1];// 初始化桶數(shù)組for (int i = 0; i <= max; i++){buckets[i] = 0;}// 將元素放入對應(yīng)的桶中for (int i = 0; i < n; i++){buckets[arr[i]]++;}// 從桶中取出元素并排序int index = 0;for (int i = 0; i <= max; i++){while (buckets[i] > 0){arr[index++] = i;buckets[i]--;}}
}int main()
{int arr[] = {5, 2, 8, 9, 1};int n = sizeof(arr) / sizeof(arr[0]);int max = 9; // 假設(shè)最大值為9printf("排序前的數(shù)組:\n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}bucket_sort(arr, n, max);printf("\n排序后的數(shù)組:\n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}putchar('\n');return 0;
}

上述代碼中，首先定義了一個bucket_sort函數(shù)，用于實現(xiàn)桶排序。這個函數(shù)接受三個參數(shù)：待排序數(shù)組arr、數(shù)組長度n和最大值max。

在函數(shù)內(nèi)部，首先創(chuàng)建了一個長度為max+1的桶數(shù)組buckets，并將其初始化為0。然后，遍歷待排序數(shù)組，將每個元素放入對應(yīng)的桶中，即對應(yīng)索引位置上的數(shù)值加1。

接下來，使用兩層循環(huán)從桶中取出元素，并按照順序存放到原始數(shù)組arr中。外層循環(huán)遍歷桶數(shù)組，內(nèi)層循環(huán)根據(jù)桶中記錄的數(shù)量，將元素按照順序放入原始數(shù)組，同時將桶中記錄數(shù)量減1。

在main函數(shù)中，定義了一個待排序的數(shù)組arr，然后調(diào)用bucket_sort函數(shù)進(jìn)行排序。最后，輸出排序前后的數(shù)組結(jié)果。

這段代碼的核心思想是按照待排序數(shù)據(jù)的取值范圍創(chuàng)建相應(yīng)數(shù)量的桶，將數(shù)據(jù)按照取值映射到桶中，并對每個桶中的數(shù)據(jù)進(jìn)行排序后，再依次取出合并為有序序列。

運(yùn)行如上代碼，你可以看到以下輸出：