排序演算法分析_ZenDei技術網路在線

我們都知道，在應屆面試的時候，問到最多的就是快速排序，快速排序是最經典、最常用的排序演算法，因為它的平均效率最優，也最穩定。快速排序使用了分治的演算法思想，分治演算法本身理解起來很符合人類的思路（遞歸是很容易被理解的），其最關鍵的一步，就是劃分了，演算法導論上介紹了一種劃分方法，和我在數據結構課上學的略有 ...

我們都知道，在應屆面試的時候，問到最多的就是快速排序，快速排序是最經典、最常用的排序演算法，因為它的平均效率最優，也最穩定。

快速排序使用了分治的演算法思想，分治演算法本身理解起來很符合人類的思路（遞歸是很容易被理解的），其最關鍵的一步，就是劃分了，演算法導論上介紹了一種劃分方法，和我在數據結構課上學的略有不同，昨晚，我把它們全都用java實現了。

這個是演算法導論的版本：

 1 /**
 2      * 快速排序的劃分方法一：演算法導論版本 sit的下一個比最後一個大
 3      * 
 4      * @param begin
 5      * @param end
 6      * @return
 7      */
 8     private int QuickMergeA(int begin, int end) {
 9         System.out.print("初始：" + arr);
10         System.out.print(begin + " " + end);
11         int anchor = (int) arr.get(end);
12         int sit = begin - 1;
13         int temp;
14         for (int i = begin; i < end; i++) {
15             if ((int) arr.get(i) <= anchor) {
16                 sit++;
17                 temp = (int) arr.get(i);
18                 arr.set(i, (int) arr.get(sit));
19                 arr.set(sit, temp);
20             }
21         }
22         temp = (int) arr.get(sit + 1);
23         arr.set(sit + 1, anchor);
24         arr.set(end, temp);
25         System.out.print(arr);
26         System.out.println(sit + 1);
27         return sit + 1;
28     }

不難看出，這個版本的劃分思路是，從數組一端往另一端推進，對於比指定元素小的值，均放在左側，比指定元素大的值，放在右側。

然後我們再看我數據結構課本上學過的版本：

/**
     * 快速排序的劃分方法二：數據結構課本版本
     * 
     * @param begin
     * @param end
     * @return
     */
    private int QuickMergeB(int begin, int end) {
        System.out.print("初始：" + arr);
        System.out.print(begin + " " + end);
        int anchor = arr.get(end);
        int send = end - 1;
        int temp;
        int tbegin = begin;
        while (begin <= send) {
            while (arr.get(begin) <= anchor && begin <= end - 1) {
                begin++;
            }
            while (send >= tbegin && arr.get(send) > anchor) {
                send--;
            }
            if (begin < send) {
                temp = arr.get(begin);
                arr.set(begin, arr.get(send));
                arr.set(send, temp);
            }
            if (begin >= send) {
                temp = arr.get(begin);
                arr.set(begin, arr.get(end));
                arr.set(end, temp);
            }
        }
        System.out.print(arr);
        System.out.println(send + 1);
        return send + 1;
    }

可以看出，這種思路是兩端推進的手段，兩端同時推進，同樣是左邊存放比指定元素小的值，右邊存放比指定元素大的值。

這兩種方法遍曆數組的推進方法雖然不同，但是其效率是一致的，劃分一次都相當於是要遍歷一次子數組。其劃分的包裝入口也是相似的：

/**
     * 快速排序入口
     * 
     * @param begin
     * @param end
     */
    private void QuickSequence(int begin, int end) {
        // if (begin < end) {
        // int q = QuickMergeA(begin, end);
        // this.QuickSequence(begin, q - 1);
        // this.QuickSequence(q + 1, end);
        // }
        if (begin < end) {
            int q = QuickMergeB(begin, end);
            this.QuickSequence(begin, q - 1);
            this.QuickSequence(q + 1, end);
        }

    }

需要指明的是，測試上面方法的過程中，應該把arr數組設置為靜態的，在java中，實現類似於C++的地址訪問的情況，我經常使用靜態變數。

最古老的排序演算法是插入排序，之前學習數據結構的時候，對於各種排序演算法總是混淆，比如對於快速排序和插入排序的演算法思路都明白，但是總是把快速排序當成插入排序，插入排序當成快速排序。也許是當時兩節課學了冒泡排序、快速排序、插入排序、堆排序等太多的排序演算法吧，加上編程經驗少造成的。

其實插入排序很容易和快速排序區分開。因為插入排序是真的“插入”。插入排序的基礎是左側數據已經排序準確，你要做的是把下一個數插入到有序數組的指定位置，你可以腦補撲克牌。

/**
     * 插入排序
     */
    private void InsertSequence() {
        for (int i = 0; i < arr.size(); i++) {
            int p = 0;
            while (p < i && arr.get(p) < arr.get(i)) {
                p++;
            }
            if (p < i) {
                int temp = arr.get(i);
                for (int k = i; k > p; k--) {
                    arr.set(k, arr.get(k - 1));
                }
                arr.set(p, temp);
            }
        }
    }

插入排序的代碼很短，但是我們的經驗是，短的代碼代表思路簡單，不代表效率高。其實是這樣的，插入排序的效率是N^2,而快速排序的效率則是NlogN。插入排序是最朴素的排序演算法，也是相對較慢的排序演算法。

學數據結構的課程時，我非常喜歡堆排序。或許是因為它是最形象的排序演算法。其實，堆排序利用特有的數據結構，高效的做了這麼一件事，每次找出最小的數，然後從數組中刪掉這個數，繼續查找。

 1 private void MaintainHeap(int length) {
 2         int temp;
 3         for (int i = length / 2 - 1; i >= 0; i--) {
 4             if ((arr.get(i) < arr.get((i + 1) * 2 - 1))
 5                     || ((i + 1) * 2 < length && arr.get(i) < arr
 6                             .get((i + 1) * 2))) {
 7                 if ((i + 1) * 2 < length) {
 8                     if (arr.get((i + 1) * 2) < arr.get((i + 1) * 2 - 1)) {
 9                         temp = arr.get(i);
10                         arr.set(i, arr.get((i + 1) * 2 - 1));
11                         arr.set((i + 1) * 2 - 1, temp);
12                     } else {
13                         temp = arr.get(i);
14                         arr.set(i, arr.get((i + 1) * 2));
15                         arr.set((i + 1) * 2, temp);
16                     }
17 
18                 } else {
19                     temp = arr.get(i);
20                     arr.set(i, arr.get((i + 1) * 2 - 1));
21                     arr.set((i + 1) * 2 - 1, temp);
22                 }
23 
24             }
25         }
26 
27         System.out.println(arr);
28     }
29 
30     private void Heapsequence(int length) {
31         for (int i = length; i > 0; i--) {
32             this.MaintainHeap(i);
33             int temp = arr.get(0);
34             arr.set(0,arr.get(i - 1));
35             arr.set(i - 1, temp);
36         }
37     }

堆排序的重要步驟是堆的維護。對於最大堆而言，要確保特定個元素構建的堆中，每個節點的值都大於其孩子節點，這通常的方法是，從最後一個有子節點的節點開始，遍歷到根節點，對於這其間的每一個結點，如果其子節點存在大於當前節點的節點，則把最大的子節點同當前節點交換，並同時維護交換後的子節點的狀態（這個子節點的子節點可能在交換後比子節點的值大）。

除了上面的排序演算法，我們常見的還有冒泡排序之類。同時，我在演算法導論上，還接觸過計數排序、基數排序、桶排序等線性排序演算法。因為其思路比較簡單，所以這裡只給出一般思路：

計數排序顧名思義，使用了一個計數數組，對於每一個值，初始計數為0，每新增一個，該計數就增加一，最後形成一個排序序列。計數排序的效率一般，但是由於其穩定，常常作為其它排序演算法基本過程的演算法使用。

基數排序是另外一種比較有意思的排序演算法，它先從最低位對數據進行排序，然後再依次上升到最高位，而對每個數位的排序，他通常使用計數排序。

桶排序是效率最高的排序演算法，但是它對數據要求較高，同時是一種以空間換時間的排序演算法。它的方案是先new一個足夠大的數組，然後對待排序數組遍歷，將新數組鍵等於待排序數組中值的位置置為一（多個則繼續增一），然後遍歷新數組，即可得到待排序數組的順序。這種演算法不適合離散性數據，也不適合不知道範圍的數據排序。

以上。