桶排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 桶排序算法
  2. 桶排序示例
  3. 桶排序算法的实现
  4. 桶排序算法的复杂度
桶排序
注意
如果你不知道什么是插入排序,请先去看插入排序一文。

桶排序是一种比较型排序算法。它通过将元素分布到桶或仓中,并使用不同的算法(通常是插入排序)对各个桶的内容进行排序。然后将各个排序后的桶加在一起,得到最终的排序数组。这种排序算法的方法也被称为分散收集法。它主要用于当输入的内容均匀分布在一个范围内,比如浮点数从 0.001.00

桶排序算法

假设我们有一个包含 n 元素的无序数组 A[]

  • 创建 k(理想的情况是 kn)个空桶,将输入的范围分成相等的部分。
  • 对于数组 A 中出现的每一个元素 A[i],执行以下操作。
  • A[i] 插入到索引为 n*A[i] 的桶中。
  • 使用插入排序算法对各个桶进行排序。
  • 按顺序检查各桶,并将排序后的桶进行连接,形成最终的排序数组。

桶排序示例

假设我们有数组:(0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31). 我们将使用桶排序算法对其进行排序。

  • 制作 10 个范围为 0.1 的桶
0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0
  • 将元素插入到桶后,我们得到,
0 1 2 3 4 5 6 7 8 9
0.1 0.22, 0.21 0.33, 0.38, 0.31 0.45 0.55
  • 对各个桶进行排序,得到。
0 1 2 3 4 5 6 7 8 9
0.1 0.21, 0.22 0.31, 0.33, 0.38 0.45 0.55

将所有的结果加在一起,我们得到最终的排序数组为。(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(n2)。因此,最坏情况下的时间复杂度为 [Big O]。O(n2)。

  • 最佳情况

最好的情况是,元素均匀分布在所有的桶中,或者我们得到一个已经排序的数组。总时间复杂度包括创建桶 O(n) 和排序 O(k) 所需的时间。最佳情况下的时间复杂度是 [Big Omega]:O(n+k)

空间复杂度

桶式排序算法最差的空间复杂度是 O(n*k),其中 n 是元素的数量,k 是桶的数量。通过减少容纳所有元素的空间和存储指向桶起始的指针,空间复杂度可以降低到 O(n+k)

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Sort Algorithm