成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

數(shù)據(jù)結(jié)構(gòu)與算法——線性排序

Allen / 2211人閱讀

摘要：實(shí)際上，桶排序的應(yīng)用場景十分的有限，對數(shù)據(jù)的要求比較苛刻。極端情況下，如果數(shù)據(jù)全部劃分到一個桶內(nèi)，就變成了非線性排序了。

1. 回顧

前面已經(jīng)說完了幾種非線性排序，它們分別是時間復(fù)雜度為 O(n2) 、適合小規(guī)模數(shù)據(jù)的冒泡排序、選擇排序、插入排序，和應(yīng)用較廣泛的時間復(fù)雜度為 O(nlogn) 的希爾排序、歸并排序、快速排序。其實(shí)這幾種排序都有一個特性，那就是它們都是基于數(shù)據(jù)的比較和移動，而今天介紹的這幾種線性排序，他們的時間復(fù)雜度都是 O(n) ，因?yàn)椴簧婕暗綌?shù)據(jù)的比較和移動。

2. 桶排序

桶排序的思路是：將要排序的數(shù)據(jù)按照一定的范圍劃分到有序的桶內(nèi)，在桶內(nèi)進(jìn)行排序，然后依次從桶中將數(shù)據(jù)取出來，這樣整個數(shù)據(jù)就有序了。

例如我們要排序一組大小在 [0 - 50] 的數(shù)據(jù)，可以劃分 5 個桶，每個桶存放的數(shù)據(jù)范圍為：[1 - 10]、[11-20]、[21 - 30] 以此類推，就像下圖這樣：

然后在將桶內(nèi)的數(shù)據(jù)排序，依次取出來，整個數(shù)據(jù)就有序了。

實(shí)際上，桶排序的應(yīng)用場景十分的有限，對數(shù)據(jù)的要求比較苛刻。首先，它要求每個桶的數(shù)據(jù)范圍是有序的，就像上面那樣依次排列，這樣才能夠保證從桶中取出的數(shù)據(jù)仍然保持有序，其次，要保證數(shù)據(jù)較為均勻的劃分到各個桶中，如果出現(xiàn)數(shù)據(jù)集中到某個或幾個桶內(nèi)，那么時間復(fù)雜度就會下降。極端情況下，如果數(shù)據(jù)全部劃分到一個桶內(nèi)，就變成了非線性排序了。

下面我模擬了一個簡單的桶排序：

public class BucketSort {

    //測試場景：數(shù)組中有10000個數(shù)據(jù)，范圍在0-100000之間
    //使用100個桶，每個桶存放的數(shù)據(jù)范圍為：0-999, 1000-1999, 2000-2999，依次類推
    public static void bucketSort(int[] data){
        //新建100個桶，使用ArrayList作為桶
        ArrayList> buckets = new ArrayList<>(100);
        for (int i = 0; i < 100; i++) {
            buckets.add(new ArrayList<>());
        }
        //遍歷數(shù)組，將數(shù)據(jù)放置到桶中
        for (int i = 0; i < data.length; i++) {
            buckets.get(data[i] / 1000).add(data[i]);
        }
        //在桶內(nèi)部進(jìn)行排序
        int k = 0;
        for (int i = 0; i < buckets.size(); i++) {
            ArrayList list = buckets.get(i);
            Integer[] integers = list.toArray(new Integer[10]);
            Arrays.sort(integers);
            //拷貝到data中
            for (int j = 0; j < integers.length; j++) {
                data[k ++] = integers[j];
            }
        }
    }
}
2. 計(jì)數(shù)排序

計(jì)數(shù)排序其實(shí)是桶排序的一種特殊情況，假如要排序的數(shù)據(jù)范圍不大，例如為 n ，那么我們可以劃分 n 個桶，每個桶內(nèi)存放數(shù)值相同的數(shù)據(jù)，然后再遍歷取出來，這樣整個數(shù)據(jù)就有序了。

例如我們需要根據(jù)年齡給 10 萬人排序，年齡的范圍其實(shí)不大，我們可以假設(shè)年齡最小為 0，最大為 120，那么我們直接劃分 121 個桶，遍歷數(shù)組，將年齡相同的數(shù)據(jù)存放到同一個桶中，然后取出來，就完成了排序。是不是很簡單呢？

這里我就不代碼演示了，和上面的桶排序非常的類似，就是沒有了桶內(nèi)排序的這個部分，你可以自己嘗試寫一下。

3. 基數(shù)排序

再來看看基數(shù)排序，假如我們要對 10 萬個手機(jī)號碼進(jìn)行排序，應(yīng)該怎么做呢？手機(jī)號碼有 11 位，太長，不適合用桶排序或是計(jì)數(shù)排序。借助于穩(wěn)定排序，我們可以從號碼的最后一位開始比較，比較 11 次。因?yàn)榻柚氖欠€(wěn)定排序，所以前面的排序順序不會被打亂，我用了一個簡單的字符數(shù)組來模擬這個過程：

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/73822.html

相關(guān)文章

  • 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和算法概念

    摘要：數(shù)據(jù)結(jié)構(gòu)程序數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。這兩部分信息組成數(shù)據(jù)元素的存儲映象，稱為結(jié)點(diǎn)。 本文涉及更多的是概念，代碼部分請參考之前寫過的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本數(shù)據(jù)結(jié)構(gòu)和查找算法 本文主要是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法概念，可能部分地方會涉及更高級的算法和算法，具體內(nèi)容以...

    fsmStudy 評論0 收藏0

  • Github標(biāo)星2w+，熱榜第一，如何用Python實(shí)現(xiàn)所有算法

    摘要：歸并排序歸并排序，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為大符號。以此類推，直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的，因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯：周素云、蔣寶尚 學(xué)會了Python基礎(chǔ)知識，想進(jìn)階一下，那就來點(diǎn)算法吧！畢竟編程語言只...

    zxhaaa 評論0 收藏0

  • 計(jì)算機(jī)二級考試-數(shù)據(jù)結(jié)構(gòu)-模擬試題

    摘要：數(shù)據(jù)結(jié)構(gòu)試題前言這里是數(shù)據(jù)結(jié)構(gòu)系列文章，主要介紹計(jì)算機(jī)二級考試中的涉及到數(shù)據(jù)結(jié)構(gòu)的知識點(diǎn)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中處處都有存在，例如編譯系統(tǒng)要使用棧散列表語法樹等操作系統(tǒng)要使用隊(duì)列存儲管理表目錄樹等等。 數(shù)據(jù)結(jié)構(gòu) 試題前言這里是 數(shù)據(jù)結(jié)構(gòu) 系列文章，主要介紹計(jì)算機(jī)二級考試中的涉及到數(shù)據(jù)結(jié)構(gòu)的知識點(diǎn) /數(shù)據(jù)結(jié)構(gòu)在計(jì)算...

    不知名網(wǎng)友 評論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 桶排序、計(jì)數(shù)排序、基數(shù)排序

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

    Awbeci 評論0 收藏0

  • PHP面試：常見查找算法一篇說透

    摘要：我們現(xiàn)在來看二分搜索算法的兩種變形插值搜索和指數(shù)搜索。插值搜索是對二分搜索算法的改進(jìn)，插值搜索可以基于搜索的值選擇到達(dá)不同的位置。 預(yù)警 在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復(fù)雜度。因?yàn)榱η笸ㄋ滓锥?，所以篇幅可能較長，大伙可以先Mark下來，每天抽時間看一點(diǎn)理解一點(diǎn)。本文配套的Github Repo，歡迎各位老鐵star，會一直更新的。 開篇 和排序類似，搜索或者叫做...

    付永剛 評論0 收藏0

發(fā)表評論

0條評論

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