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 阅读(3731) 评论(2)  编辑  收藏 所属分类: 计算机科学基础