快捷導(dǎo)航

JAVA十大排序算法之桶排序詳解

更新時(shí)間：2021年08月23日 10:54:40 作者：阿粵Ayue

這篇文章主要介紹了java中的桶排序，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

桶排序

桶排序是計(jì)數(shù)排序的升級(jí)，計(jì)數(shù)排序可以看成每個(gè)桶只存儲(chǔ)相同元素，而桶排序每個(gè)桶存儲(chǔ)一定范圍的元素，通過函數(shù)的某種映射關(guān)系，將待排序數(shù)組中的元素映射到各個(gè)對(duì)應(yīng)的桶中，對(duì)每個(gè)桶中的元素進(jìn)行排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序），最后將非空桶中的元素逐個(gè)放入原序列中。

桶排序需要盡量保證元素分散均勻，否則當(dāng)所有數(shù)據(jù)集中在同一個(gè)桶中時(shí)，桶排序失效。

代碼實(shí)現(xiàn)

1.找出數(shù)組中的最大值max和最小值min，可以確定出數(shù)組所在范圍min~max

2.根據(jù)數(shù)據(jù)范圍確定桶的數(shù)量

1.若桶的數(shù)量太少，則桶排序失效

2.若桶的數(shù)量太多，則有的桶可能，沒有數(shù)據(jù)造成空間浪費(fèi)

所以桶的數(shù)量由我們自己來確定，但盡量讓元素平均分布到每一個(gè)桶里，這里提供一個(gè)方式

(最大值 - 最小值)/每個(gè)桶所能放置多少個(gè)不同數(shù)值+1

3.確定桶的區(qū)間，一般是按照(最大值 - 最小值)/桶的數(shù)量來劃分的，且左閉右開

public class BucketSort {
    public static final int[] ARRAY = {35, 23, 48, 9, 16, 24, 5, 11, 32, 17};
    /**
     * @param bucketSize 作為每個(gè)桶所能放置多少個(gè)不同數(shù)值,即數(shù)值的類型
     *                   例如當(dāng)BucketSize==5時(shí)，該桶可以存放｛1,2,3,4,5｝這幾種數(shù)字，
     *                   但是容量不限，即可以存放100個(gè)3
     */
    public static List<Integer> sort(List<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2)
            return array;
        int max = array.get(0), min = array.get(0);
        // 找到最大值最小值
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i) > max)
                max = array.get(i);
            if (array.get(i) < min)
                min = array.get(i);
        }
        //獲取桶的數(shù)量
        int bucketCount = (max - min) / bucketSize + 1;
        //構(gòu)建桶，初始化
        List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        List<Integer> resultArr = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<>());
        }
        //將原數(shù)組的數(shù)據(jù)分配到桶中
        for (int i = 0; i < array.size(); i++) {
            //區(qū)間范圍
            bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
        }
        for (int i = 0; i < bucketCount; i++) {
            if (bucketSize == 1) {
                for (int j = 0; j < bucketArr.get(i).size(); j++)
                    resultArr.add(bucketArr.get(i).get(j));
            } else {
                if (bucketCount == 1)
                    bucketSize--;
                //對(duì)桶中的數(shù)據(jù)再次用桶進(jìn)行排序
                List<Integer> temp = sort(bucketArr.get(i), bucketSize);
                for (int j = 0; j < temp.size(); j++)
                    resultArr.add(temp.get(j));
            }
        }
        return resultArr;
    }
    public static void print(List<Integer> array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()));
        System.out.println("============================================");
        print(sort(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()), 2));
    }
}