桶排序

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