gr8vyguy@Blogjava

Insertion-Sort和Merge-Sort

Insertion-Sort和Merge-Sort是兩種非常有代表性的排序算法。Insertion-Sort逐個將未排序的元素插入到正確的位置，下面這張圖很形象的描述了Insertion-Sort.

所以Insertion-Sort也是一種incremental的算法。Merge-Sort采用一種完全不同的方式，即是divide-and-conquer, 將元素分成兩組，先分別將這兩組排好序，然后再組合起來，就如下圖所示，

Insertion-Sort

/**
     * sort A in nondecreasing order
     * 
     * @param A
     *            The array to sorted
     */
    public static void sort(int[] A) {
            sort(A, 0, A.length - 1);
        }

    public static void sort(int[] A, int p, int r) {
        for (int j = p + 1; j <= r; j++) {
                  int key = A[j];
                  // Insert A[j] into the sorted sequence A[0 .. j-1]
                  int i = j - 1;
              while (i >= p && A[i] > key) {
                        A[i + 1] = A[i];
                        i = i - 1;
                  }
                 A[i + 1] = key;
            }
       }

Merge-Sort

/**
     * Sort A[p .. r] with Merge Sort
     */
  public static void mergeSort(int[] A, int p, int r) {
        if (p < r) {
                  int q = (p + r) / 2;
                  mergeSort(A, p, q);
                  mergeSort(A, q + 1, r);
                  merge(A, p, q, r);
            }
      }

merge函數

/**
     * merge sorted A[p .. q] and A[q+1 .. r] into A[p .. r]
     */
    private static void merge(int[] A, int p, int q, int r) {
              int[] L = new int[q - p + 1];
              int[] R = new int[r - q];
          for (int i = 0; i < L.length; i++) {
                    L[i] = A[p + i];
             }
          for (int j = 0; j < R.length; j++) {
                   R[j] = A[q + 1 + j];
             }
        
             int i = 0;
             int j = 0;
             int k = p;
         while (i < L.length && j < R.length) {
              if (L[i] < R[j]) {
                      A[k++] = L[i++];
              } else {
                      A[k++] = R[j++];
                 }
            }
         while (i < L.length) {
                 A[k++] = L[i++];
             }
         while (j < R.length) {
                A[k++] = R[j++];
            }
     }

復雜度分析

最差情況下Insertion-Sort的復雜度是O(n²), 而Merge-Sort是O(nlgn)。就是說Merge-Sort比Insertion-Sort好了一個n對lgn的程度，相差大嗎？當然是n越大，Merge-Sort相比于Insertion-Sort的優勢越明顯。有多明顯呢？做個實驗看看，將一百萬個整數排序。在我的電腦上，Merge-Sort用了731 ms，而Insertion-Sort跑了5分鐘還沒出來，就不等了，沒這個耐心。不過可以估算大概需要多長時間。Insertion-Sort排10000個整數所需的時間
T(10000)=191 ms，假設T(n) = cn^2.

Insertion-Sort和Merge-Sort的結合

雖然Insertion-Sort是平方級的復雜度，而Merge-Sort是nlgn級的復雜度，但是當n比較小的時候，Insertion-Sort反而要快一些，因為復雜度分析是一種增長級速的分析，對大的輸入情況才有意義。既然n小的時候，Insertion-Sort比Merge-Sort要快，那么一個改善Merge-Sort的方法就呼之欲出了。當divide(回歸調用)到一定程度的時候，即元素個數小于某個值K的時候，用Insertion-Sort排序。這種算法可以稱作Insertion-Merge-Sort.

Insertion-Merge-Sort的Java實現

    public static void sort(int[] A) {
            mergeSort(A, 0, A.length - 1);
       }

    private static void mergeSort(int[] A, int p, int r) {
        if (r - p + 1 <= K) {
                 InsertionSort.sort(A, p, r);
        } else {
                int q = (p + r) / 2;
                mergeSort(A, p, q);
                mergeSort(A, q + 1, r);
                merge(A, p, q, r);
          }
       }

    private static void merge(int[] A, int p, int q, int r) {
            int n1 = q - p + 1;
            int n2 = r - q;
            int[] L = new int[n1 + 1];
            int[] R = new int[n2 + 1];
        for (int i = 0; i < n1; i++) {
               L[i] = A[p + i];
           }
           L[n1] = Integer.MAX_VALUE; // put the sentinel
        for (int j = 0; j < n2; j++) {
              R[j] = A[q + 1 + j];
            }
           R[n2] = Integer.MAX_VALUE;
           int i = 0;
           int j = 0;
       for (int k = p; k <= r; k++) {
            if (L[i] < R[j]) {
                     A[k] = L[i];
                     i = i + 1;
            } else {
                    A[k] = R[j];
                    j = j + 1;
                }
           }
    }

Insertion-Merge-Sort比Merge-Sort快多少? 用Insertion-Merge-Sort對一百萬個整數排序需要大約541ms. 相比于Merge-Sort的731ms，快了將近26%.

Insertion-Merge-Sort的復雜度分析

假設當輸入個數為K時，采用Insertion-Sort, 那么有n/K個小組要用Insertion-Sort，所需時間為，
n/K * K²=nK, 將n/K個小組組合起來，所需的時間是n*lg(n/K), 那么加起來就是Insertion-Merge-Sort的復雜度O(nK + nlg(n/K)).

還有一個問題，某個值K應該取多大才算是最合適呢? 

當K=1時，Insertion-Merge-Sort就成了Merge-Sort， 當K=n時，Insertion-Merge-Sort就成了Insertion-Sort。理論上，K的取值不應該使得Insertion-Merge-Sort的復雜度高于Merge-Sort的復雜度即O(nlgn), 如果按這個要求推理，那么K應該屬于O(lgn)。 在實踐中，K可以取所有Insertion-Sort還比Merge-Sort快的最大值。但是在不同的計算環境和不同的輸入下，這個值也會不一樣。我們只能根據實驗的情況取一個多數情況下比較好的K值。Java的Arrays.sort(.)函數取的是7，你可以看JDK的源代碼。好像Java的Arrays類以前用的是Quick-Sort算法, 不知道什么時候換成Insertion-Merge-Sort了。

本文所有源代碼。

注腳
以上所有的復雜度實際上即是上限，也是下限，習慣上應該用Theta表示，而O一般只表示一個上限，由于Theta不好打，只好這樣了，而且O的知名度要高很多，也被人濫用了很多。具體參照Knuth的論文Big Omicron and big Omega and big Theta。

posted on 2007-04-28 22:36 gr8vyguy 閱讀(3767) 評論(2)  編輯  收藏 所屬分類: 計算機科學基礎