計數(shù)排序的優(yōu)點有哪些

這篇文章主要介紹“計數(shù)排序的優(yōu)點有哪些”，在日常操作中，相信很多人在計數(shù)排序的優(yōu)點有哪些問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”計數(shù)排序的優(yōu)點有哪些”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

計數(shù)排序

計數(shù)排序是一個非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優(yōu)勢在于在對一定范圍內的整數(shù)排序時， 它的復雜度為Ο(n+k)（其中k是整數(shù)的范圍），快于任何比較排序算法。 [1] 當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(nlog(n))的時候其效率反而不如基于比較的排序 （基于比較的排序的時間復雜度在理論上的下限是O(nlog(n)), 如歸并排序，堆排序）

算法思想

計數(shù)排序對輸入的數(shù)據有附加的限制條件： 1、輸入的線性表的元素屬于有限偏序集S； 2、設輸入的線性表的長度為n，|S|=k（表示集合S中元素的總數(shù)目為k），則k=O(n)。 在這兩個條件下，計數(shù)排序的復雜性為O(n)。 計數(shù)排序的基本思想是對于給定的輸入序列中的每一個元素x，確定該序列中值小于x的元素的個數(shù)（此處并非比較各元素的大小，而是通過對元素值的計數(shù)和計數(shù)值的累加來確定）。 一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個元素的值小于x的值，則x可以直接存放在輸出序列的第18個位置上。 當然，如果有多個元素具有相同的值時，我們不能將這些元素放在輸出序列的同一個位置上，因此，上述方案還要作適當?shù)男薷?/p>

算法思想

計數(shù)排序是一種穩(wěn)定的排序算法,它能在線性時間 (O(n+k)) 內對包含n個元素的數(shù)組進行排序,其中數(shù)組元素均大于等于 0 且小于等于 k。

對輸入數(shù)組 A的各個元素A[x]進行排序時,我們先將A[x]的元素個數(shù)記錄在計數(shù)數(shù)組C中, 然后根據C中的數(shù)值計算在輸出數(shù)組B中的位置。 考慮到存在多個相等元素的情況,再維護了B中的數(shù)據同時，如果A中存在相同的數(shù)據需要在B中相應減去一。

代碼實現(xiàn)

public static int[] countSort(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int[] res = new int[arr.length];
        //O(n)
        for (int j : arr) {
            min = Math.min(j, min);
            max = Math.max(j, max);
        }
        int[] pos = new int[max + 1];
        //O(k)
        for (int i = 0; i < arr.length; i++) {
            //因為此處計數(shù)是從 1 開始的。
            pos[arr[i]]++;
        }
        for (int i = 1; i < pos.length; i++) {
            pos[i] = pos[i] + pos[i - 1];
        }
        for (int i = 0; i < arr.length; i++) {
            //計數(shù)是從 1開始的，我們重新排res[]應該從0開始
            res[pos[arr[i]]-1] = arr[i];
            pos[arr[i]]--;
        }
        return res;
    }

總結

• 計數(shù)排序本質就是用數(shù)組存儲一個映射關系把它的位置保存起來，然后再遍歷原先的數(shù)組從位置數(shù)組中把它拿出來進行排序。

• 所排序的數(shù)組中必須為非負整數(shù)，因為數(shù)組的下標被限制了。

• 計數(shù)排序時間復雜度為O(n+k),n 為待排序的長度，k為數(shù)組的中元素最大值。

到此，關于“計數(shù)排序的優(yōu)點有哪些”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>