欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2021年08月23日 10:54:40   作者:阿粵Ayue  
這篇文章主要介紹了java中的桶排序,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下

桶排序

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

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

image-20210808133137559

代碼實現(xiàn)

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

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

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

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

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

(最大值 - 最小值)/每個桶所能放置多少個不同數(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 作為每個桶所能放置多少個不同數(shù)值,即數(shù)值的類型
     *                   例如當(dāng)BucketSize==5時,該桶可以存放{1,2,3,4,5}這幾種數(shù)字,
     *                   但是容量不限,即可以存放100個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--;
                //對桶中的數(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));
    }
}

時間復(fù)雜度

桶排序算法遍歷了2次原始數(shù)組,運算量為2N,最后,遍歷桶輸出排序結(jié)果的運算量為N,初始化桶的運算量為M。

對桶進(jìn)行排序,不同的排序算法算法復(fù)雜度不同,冒泡排序算法復(fù)雜度為O(N^2),堆排序、歸并排序算法復(fù)雜度為O(NlogN),我們以排序算法復(fù)雜度為O(NlogN)進(jìn)行計算,運算量為N/M * log(N/M) * M

最終的運算量為3N+M+N/M * log(N/M) * M,即3N+M+N(logN-logM),去掉系數(shù),時間復(fù)雜度為O(N+M+N(logN-logM))

算法穩(wěn)定性

桶排序算法在對每個桶進(jìn)行排序時,若選擇穩(wěn)定的排序算法,則排序后,相同元素的位置不會發(fā)生改變,所以桶排序算法是一種穩(wěn)定的排序算法。

總結(jié)

本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

  • 使用JPA自定義id策略避免主鍵自增

    使用JPA自定義id策略避免主鍵自增

    這篇文章主要介紹了使用JPA自定義id策略避免主鍵自增問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-08-08
  • SpringBoot整合Jackson超詳細(xì)用法(附Jackson工具類)

    SpringBoot整合Jackson超詳細(xì)用法(附Jackson工具類)

    這篇文章主要介紹了SpringBoot整合Jackson超詳細(xì)教程,本篇講的是Jackson的詳細(xì)用法,Jackson工具類在文章最后,直接復(fù)制粘貼即可使用,需要的朋友可以參考下
    2023-03-03
  • 解決Map集合使用get方法返回null拋出空指針異常問題

    解決Map集合使用get方法返回null拋出空指針異常問題

    這篇文章主要介紹了解決Map集合使用get方法返回null拋出空指針異常問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-09-09
  • Java多線程實現(xiàn)的兩種方式

    Java多線程實現(xiàn)的兩種方式

    本文主要介紹了Java多線程實現(xiàn)的兩種方式:繼承Thread類、實現(xiàn)Runnable接口。具有一定的參考價值,下面跟著小編一起來看下吧
    2017-01-01
  • java使用任務(wù)架構(gòu)執(zhí)行任務(wù)調(diào)度示例

    java使用任務(wù)架構(gòu)執(zhí)行任務(wù)調(diào)度示例

    在Java 5.0之前啟動一個任務(wù)是通過調(diào)用Thread類的start()方法來實現(xiàn)的,5.0里提供了一個新的任務(wù)執(zhí)行架構(gòu)使你可以輕松地調(diào)度和控制任務(wù)的執(zhí)行,并且可以建立一個類似數(shù)據(jù)庫連接池的線程池來執(zhí)行任務(wù),下面看一個示例
    2014-01-01
  • Spring Boot運行部署過程圖解

    Spring Boot運行部署過程圖解

    這篇文章主要介紹了Spring Boot運行部署過程圖解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-02-02
  • java調(diào)用webservice接口,并解析返回參數(shù)問題

    java調(diào)用webservice接口,并解析返回參數(shù)問題

    這篇文章主要介紹了java調(diào)用webservice接口,并解析返回參數(shù)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-07-07
  • Java反射與Fastjson的危險反序列化詳解

    Java反射與Fastjson的危險反序列化詳解

    在?Java?中,Computer.class是一個引用,它表示了?Computer?的字節(jié)碼對象(Class對象),這個對象被廣泛應(yīng)用于反射、序列化等操作中,那么為什么?parseObject?需要這個引用呢,帶著這個問題我們一起通過本文學(xué)習(xí)下吧
    2024-07-07
  • Java統(tǒng)計代碼的執(zhí)行時間的N種方法

    Java統(tǒng)計代碼的執(zhí)行時間的N種方法

    在日常開發(fā)中經(jīng)常需要測試一些代碼的執(zhí)行時間,但又不想使用向 JMH(Java?Microbenchmark Harness,Java 微基準(zhǔn)測試套件)這么重的測試框架,所以本文就匯總了一些 Java 中比較常用的執(zhí)行時間統(tǒng)計方法,總共包含以下 6 種,需要的朋友可以參考下
    2022-08-08
  • JAVA中String類與StringBuffer類的區(qū)別

    JAVA中String類與StringBuffer類的區(qū)別

    這篇文章主要為大家詳細(xì)介紹了JAVA中String類與StringBuffer類的區(qū)別,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2016-12-12

最新評論