桶排序

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