Java算法之桶排序Bucket?Sort詳解

更新時間：2023年10月31日 08:36:58 作者：Kant101

這篇文章主要介紹了Java算法之桶排序Bucket?Sort詳解,桶排序（Bucket?Sort）又稱箱排序,是一種比較常用的排序算法,其算法原理是將數組分到有限數量的桶里,再對每個桶分別排好序,最后一次將每個桶中排好序的數輸出,需要的朋友可以參考下

1. 概述

桶排序（Bucket Sort）又稱箱排序，是一種比較常用的排序算法。其算法原理是將數組分到有限數量的桶里，再對每個桶分別排好序（可以是遞歸使用桶排序，也可以是使用其他排序算法將每個桶分別排好序），最后一次將每個桶中排好序的數輸出。

2. 算法詳解

桶排序的思想就是把待排序的數盡量均勻地放到各個桶中，再對各個桶進行局部的排序，最后再按序將各個桶中的數輸出，即可得到排好序的數。

1.首先確定桶的個數。因為桶排序最好是將數據均勻地分散在各個桶中，那么桶的個數最好是應該根據數據的分散情況來確定。首先找出所有數據中的最大值mx和最小值mn；

根據mx和mn確定每個桶所裝的數據的范圍 size，有 size = (mx - mn) / n + 1，n為數據的個數，需要保證至少有一個桶，故而需要加個1；

求得了size即知道了每個桶所裝數據的范圍，還需要計算出所需的桶的個數cnt，有 cnt = (mx - mn) / size + 1，需要保證每個桶至少要能裝1個數，故而需要加個1；

2.求得了size和cnt后，即可知第一個桶裝的數據范圍為 [mn, mn + size)，第二個桶為 [mn + size, mn + 2 * size)，…，以此類推因此步驟2中需要再掃描一遍數組，將待排序的各個數放進對應的桶中。

3.對各個桶中的數據進行排序，可以使用其他的排序算法排序，例如快速排序；也可以遞歸使用桶排序進行排序；

4.將各個桶中排好序的數據依次輸出，最后得到的數據即為最終有序。

例子

例如，待排序的數為：3, 6, 9, 1

1）求得 mx = 9，mn = 1，n = 4 size = （9 - 1) / n + 1 = 3 cnt = (mx - mn) / size + 1 = 3

2）由上面的步驟可知，共3個桶，每個桶能放3個數，第一個桶數的范圍為 [1, 4)，第二個[4, 7)，第三個[7, 10) 掃描一遍待排序的數，將各個數放到其對應的桶中，放完后如下圖所示：

3）對各個桶中的數進行排序，得到如下圖所示：

4）依次輸出各個排好序的桶中的數據，即為：1, 3, 6, 9 可見，最終得到了有序的排列。

3. 測試

JAVA

import java.util.ArrayList;

/**
 * @author yumu
 * @date 2022/8/25
 */
public class BucketSort {

    public void bucketSort(int[] nums) {
        int n = nums.length;
        int mn = nums[0], mx = nums[0];
        // 找出數組中的最大最小值
        for (int i = 1; i < n; i++) {
            mn = Math.min(mn, nums[i]);
            mx = Math.max(mx, nums[i]);
        }
        int size = (mx - mn) / n + 1; // 每個桶存儲數的范圍大小，使得數盡量均勻地分布在各個桶中，保證最少存儲一個
        int cnt = (mx - mn) / size + 1; // 桶的個數，保證桶的個數至少為1
        List<Integer>[] buckets = new List[cnt]; // 聲明cnt個桶
        for (int i = 0; i < cnt; i++) {
            buckets[i] = new ArrayList<>();
        }
        // 掃描一遍數組，將數放進桶里
        for (int i = 0; i < n; i++) {
            int idx = (nums[i] - mn) / size;
            buckets[idx].add(nums[i]);
        }
        // 對各個桶中的數進行排序，這里用庫函數快速排序
        for (int i = 0; i < cnt; i++) {
            buckets[i].sort(null); // 默認是按從小打到排序
        }
        // 依次將各個桶中的數據放入返回數組中
        int index = 0;
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                nums[index++] = buckets[i].get(j);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {19, 27, 35, 43, 31, 22, 54, 66, 78};
        BucketSort bucketSort = new BucketSort();
        bucketSort.bucketSort(nums);
        for (int num: nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

class BucketSort {
public:
    void bucketSort(vector<int> &nums) {
        int n = nums.size();
        int mn = nums[0], mx = nums[0];
        for (int i = 1; i < n; i++) {
            mn = min(mn, nums[i]);
            mx = max(mx, nums[i]);
        }
        int size = (mx - mn) / n + 1;   // size 至少要為1
        int cnt = (mx - mn) / size + 1; // 桶的個數至少要為1
        vector<vector<int>> buckets(cnt);
        for (int i = 0; i < n; i++) {
            int idx = (nums[i] - mn) / size;
            buckets[idx].push_back(nums[i]);
        }
        for (int i = 0; i < cnt; i++) {
            sort(buckets[i].begin(), buckets[i].end());
        }
        int index = 0;
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                nums[index++] = buckets[i][j];
            }
        }
    }
};


int main() {
    vector<int> nums = {19, 27, 35, 43, 31, 22, 54, 66, 78};
    BucketSort().bucketSort(nums);
    for (auto num: nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}