国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Java數據結構與算法——桶排序

DandJ / 549人閱讀

摘要：實際排序中，通常對每個桶中的元素繼續使用其他排序算法進行排序，所以更多時候，桶排序會結合其他排序算法一起使用。

聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。

前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本文從最簡單的一個排序算法——桶排序開始，分析桶排序的實現思路，代碼實現，性能特點以及適用場景。

0、其他排序算法索引(待更)

java數據結構與算法——快速排序
java數據結構與算法——插入排序

1、桶排序思想

一個簡單例子：
對6個人的英語測試成績（1~10分）進行排序。假如分數是[6,5,8,8,10,9],用桶排序的思想就是準備10個桶，編號依次為1~10，將成績放入對應的桶中，例如6分放入6號桶，兩個8分放入8號桶...然后按照桶的標號順序逐一輸出（有就輸出，沒有就不輸出），這就是桶排序的基本思想。

事實上，這只是一個簡易版，試想一下，如果待排序的元素跨度范圍比較大，例如1~10000，是不是需要10000個桶？實際上這種情況下，一個桶里并非總放一個元素，很多時候一個桶里放多個元素。其實真正的桶排序和散列表有一樣的原理。

實際排序中，通常對每個桶中的元素繼續使用其他排序算法進行排序，所以更多時候，桶排序會結合其他排序算法一起使用。

2、桶排序代碼

在分析了桶排序的思想后，首先要知道待排序元素的范圍，以上述為例，聲明一個長度為10的數組作為10個桶，然后將成績逐一往桶中放時，該桶的值+1，最終輸出倒序輸出數組下標，數組每個位置的值為幾就輸出幾次，這樣就能實現基本的桶排序。

public class BucketSort {
    private int[] buckets;
    private int[] array;
    
    public BucketSort(int range,int[] array){
        this.buckets = new int[range];
        this.array = array;
    }
    
    /*排序*/
    public void sort(){
        if(array!=null && array.length>1){
            for(int i=0;i=0; i--){
            for(int j=0;j

測試代碼：


public class SortTest {
    public static void main(String[] args) {
        testBucketsSort();
    }
    
    private static void testBucketsSort(){
        int[] array = {5,7,3,5,4,8,6,4,1,2};
        BucketSort bs = new BucketSort(10, array);
        bs.sort();
        bs.sortOut();//輸出打印排序
    }
}

3、桶排序性能特點

桶排序實際上只需要遍歷一遍所有的待排元素，然后依次放入指定的位置。如果加上輸出排序的時間，就要遍歷所有的桶。因此桶排序的時間復雜度是O(n+m),n是待排元素的個數，m是桶的個數，也就是待排元素的范圍。這個算法算是相當快的排序算法了，但是空間復雜度比較大。


當待排元素的大小范圍比較大，但待排元素個數比較少時，空間浪費就比較嚴重，待排元素分布月均勻，空間利用率越高，事實上這種情況很少見。


通過以上性能分析，可以得出桶排序的特點：速度快且簡單，但同時空間利用率較低。當待排數據跨度很大時，空間利用率是無法忍受的。

4、桶排序適用場景

根據桶排序的特點，桶排序一般適用于一些特定的環境，比如數據范圍較為局限或者有一些特定的要求，比如需要通過哈希映射快速獲取某些值，需要統計每個數的數量。但是這一切都以確認數據的范圍為前提，如果范圍跨度過大，則考慮用其他算法。

其他排序算法索引(待更)

java數據結構與算法——快速排序
java數據結構與算法——插入排序


碼字不易，如對您有幫助，歡迎點贊收藏打賞^_^

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71088.html

相關文章

  • 面試算法實踐與國外大廠習題指南

    摘要：面試算法實踐與國外大廠習題指南翻譯自維護的倉庫，包含了在線練習算法概述與大廠習題實戰等內容。面試算法實踐與國外大廠習題指南在線練習在線面試編程數據結構鏈表即是由節點組成的線性集合，每個節點可以利用指針指向其他節點。 面試算法實踐與國外大廠習題指南 翻譯自 Kevin Naughton Jr. 維護的倉庫 interviews，包含了在線練習、算法概述與大廠習題實戰等內容。筆者發現正好和...

    genedna 評論0 收藏0

  • JavaScript 數據結構與算法之美 - 桶排序、計數排序、基數排序

    摘要：之所以把計數排序桶排序基數排序放在一起比較，是因為它們的平均時間復雜度都為。動畫計數排序思想找出待排序的數組中最大和最小的元素。桶排序計數排序能派上用場嗎手機號碼有位，范圍太大，顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法為王。 想學好前端，先練好內功，只有內功深厚者...

    Awbeci 評論0 收藏0

  • JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

    摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學好前端，先練好內功，內功不行，就...

    zsy888 評論0 收藏0

  • 數據結構與算法——線性排序

    摘要：實際上，桶排序的應用場景十分的有限，對數據的要求比較苛刻。極端情況下，如果數據全部劃分到一個桶內，就變成了非線性排序了。 1. 回顧 前面已經說完了幾種非線性排序，它們分別是時間復雜度為 O(n2) 、適合小規模數據的冒泡排序、選擇排序、插入排序，和應用較廣泛的時間復雜度為 O(nlogn) 的希爾排序、歸并排序、快速排序。其實這幾種排序都有一個特性，那就是它們都是基于數據的比較和移動...

    Allen 評論0 收藏0

  • Java數據結構與算法——插入排序

    摘要：當序列本身有序時，插入排序的時間復雜度為。因為此時的分區內數據往往是近似有序的，所以使用快排并不一定優于插入排序。 聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。 前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇文章介紹排序算法中插入排序算法，包括插入排序的思路，適用場景，性能分析，java代碼等 0、其他排序算法索引(待更) java數據結構與算法——快速...

    騫諱護 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<