桶排序

1. 桶排序演算法
2. 桶排序示例
3. 桶排序演算法的實現
4. 桶排序演算法的複雜度

桶排序是一種比較型排序演算法。它通過將元素分佈到桶或倉中，並使用不同的演算法（通常是插入排序）對各個桶的內容進行排序。然後將各個排序後的桶加在一起，得到最終的排序陣列。這種排序演算法的方法也被稱為分散收集法。它主要用於當輸入的內容均勻分佈在一個範圍內，比如浮點數從 0.00 到 1.00。

桶排序演算法

假設我們有一個包含 n 元素的無序陣列 A[]。

桶排序示例

假設我們有陣列：(0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31). 我們將使用桶排序演算法對其進行排序。

• 製作 10 個範圍為 0.1 的桶

• 將元素插入到桶後，我們得到，

• 對各個桶進行排序，得到。

將所有的結果加在一起，我們得到最終的排序陣列為。(0.1,0.21,0.22,0.31,0.33,0.38,0.45,0.55)。

桶排序演算法的實現

#include <bits/stdc++.h>
using namespace std;

void bucketSort(float *array, int size) {
  vector<float> bucket[size];
  // insert elements into different buckets.
  for (int i = 0; i < size; i++) {
    bucket[int(size * array[i])].push_back(array[i]);
  }
  // sort individual buckets.
  for (int i = 0; i < size; i++) {
    sort(bucket[i].begin(), bucket[i].end());
  }

  int index = 0;
  for (int i = 0; i < size; i++) {
    while (!bucket[i].empty()) {
      array[index++] = *(bucket[i].begin());
      bucket[i].erase(bucket[i].begin());
    }
  }
}

int main() {
  int n = 8;
  float arr[8] = {0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bucketSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

桶排序演算法的複雜度

時間複雜度

• 平均情況

如果元素是隨機分佈的，則會出現平均情況，該演算法可以得到非常有效的結果。時間複雜度為[大 Theta]量級：O(n+k)。它是少數幾個具有平均線性時間複雜度的演算法之一，如果桶大小的平方和是線性的 n，這個複雜度就會成立。

• 最壞情況

最壞的情況發生在許多元素在陣列中距離很近的情況下，並被聚集在同一個桶中。它剝奪了將輸入劃分到桶中的所有優勢，總複雜度變得取決於所使用的排序演算法。當元素順序相反時，插入排序的最壞情況時間複雜度為 O(n²)。因此，最壞情況下的時間複雜度為 [Big O]。O(n²)。

• 最佳情況

最好的情況是，元素均勻分佈在所有的桶中，或者我們得到一個已經排序的陣列。總時間複雜度包括建立桶 O(n) 和排序 O(k) 所需的時間。最佳情況下的時間複雜度是 [Big Omega]：O(n+k)。

空間複雜度

桶式排序演算法最差的空間複雜度是 O(n*k)，其中 n 是元素的數量，k 是桶的數量。通過減少容納所有元素的空間和儲存指向桶起始的指標，空間複雜度可以降低到 O(n+k)。