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

資訊專欄INFORMATION COLUMN

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

Allen / 2209人閱讀

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

1. 回顧

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

2. 桶排序

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

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

然后在將桶內的數據排序，依次取出來，整個數據就有序了。

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

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

public class BucketSort {

    //測試場景：數組中有10000個數據，范圍在0-100000之間
    //使用100個桶，每個桶存放的數據范圍為：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<>());
        }
        //遍歷數組，將數據放置到桶中
        for (int i = 0; i < data.length; i++) {
            buckets.get(data[i] / 1000).add(data[i]);
        }
        //在桶內部進行排序
        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. 計數排序

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

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

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

3. 基數排序

再來看看基數排序，假如我們要對 10 萬個手機號碼進行排序，應該怎么做呢？手機號碼有 11 位，太長，不適合用桶排序或是計數排序。借助于穩定排序，我們可以從號碼的最后一位開始比較，比較 11 次。因為借助的是穩定排序，所以前面的排序順序不會被打亂，我用了一個簡單的字符數組來模擬這個過程：

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

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

相關文章

  • 基礎數據結構和算法概念

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

    fsmStudy 評論0 收藏0

  • Github標星2w+，熱榜第一，如何用Python實現所有算法

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

    zxhaaa 評論0 收藏0

  • 計算機二級考試-數據結構-模擬試題

    摘要：數據結構試題前言這里是數據結構系列文章，主要介紹計算機二級考試中的涉及到數據結構的知識點數據結構在計算機科學中處處都有存在，例如編譯系統要使用棧散列表語法樹等操作系統要使用隊列存儲管理表目錄樹等等。 數據結構 試題前言這里是 數據結構 系列文章，主要介紹計算機二級考試中的涉及到數據結構的知識點 /數據結構在計算...

    不知名網友 評論0 收藏0

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

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

    Awbeci 評論0 收藏0

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

    摘要：我們現在來看二分搜索算法的兩種變形插值搜索和指數搜索。插值搜索是對二分搜索算法的改進，插值搜索可以基于搜索的值選擇到達不同的位置。 預警 在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復雜度。因為力求通俗易懂，所以篇幅可能較長，大伙可以先Mark下來，每天抽時間看一點理解一點。本文配套的Github Repo，歡迎各位老鐵star，會一直更新的。 開篇 和排序類似，搜索或者叫做...

    付永剛 評論0 收藏0

發表評論

0條評論

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