Insertion-Sort和Merge-Sort是兩種非常有代表性的排序算法。Insertion-Sort逐個(gè)將未排序的元素插入到正確的位置，下面這張圖很形象的描述了Insertion-Sort.
所以Insertion-Sort也是一種incremental的算法。Merge-Sort采用一種完全不同的方式，即是divide-and-conquer, 將元素分成兩組，先分別將這兩組排好序，然后再組合起來，就如下圖所示，
Java實(shí)現(xiàn)
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函數(shù)
/**
* 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++];
}
}
復(fù)雜度分析
最差情況下Insertion-Sort的復(fù)雜度是O(n2), 而Merge-Sort是O(nlgn)。就是說Merge-Sort比Insertion-Sort好了一個(gè)n對(duì)lgn的程度，相差大嗎？當(dāng)然是n越大，Merge-Sort相比于Insertion-Sort的優(yōu)勢(shì)越明顯。有多明顯呢？做個(gè)實(shí)驗(yàn)看看，將一百萬個(gè)整數(shù)排序。在我的電腦上，Merge-Sort用了731 ms，而Insertion-Sort跑了5分鐘還沒出來，就不等了，沒這個(gè)耐心。不過可以估算大概需要多長(zhǎng)時(shí)間。Insertion-Sort排10000個(gè)整數(shù)所需的時(shí)間
T(10000)=191 ms，假設(shè)T(n) = cn^2.
約需32分鐘，如果你有興趣可以在你的電腦上試試看，所有的源代碼和測(cè)試程序可以在下面下載。
Insertion-Sort和Merge-Sort的結(jié)合
雖然Insertion-Sort是平方級(jí)的復(fù)雜度，而Merge-Sort是nlgn級(jí)的復(fù)雜度，但是當(dāng)n比較小的時(shí)候，Insertion-Sort反而要快一些，因?yàn)閺?fù)雜度分析是一種增長(zhǎng)級(jí)速的分析，對(duì)大的輸入情況才有意義。既然n小的時(shí)候，Insertion-Sort比Merge-Sort要快，那么一個(gè)改善Merge-Sort的方法就呼之欲出了。當(dāng)divide(回歸調(diào)用)到一定程度的時(shí)候，即元素個(gè)數(shù)小于某個(gè)值K的時(shí)候，用Insertion-Sort排序。這種算法可以稱作Insertion-Merge-Sort.
Insertion-Merge-Sort的Java實(shí)現(xiàn)
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對(duì)一百萬個(gè)整數(shù)排序需要大約541ms. 相比于Merge-Sort的731ms，快了將近26%.
Insertion-Merge-Sort的復(fù)雜度分析
假設(shè)當(dāng)輸入個(gè)數(shù)為K時(shí)，采用Insertion-Sort, 那么有n/K個(gè)小組要用Insertion-Sort，所需時(shí)間為，
n/K * K2=nK, 將n/K個(gè)小組組合起來，所需的時(shí)間是n*lg(n/K), 那么加起來就是Insertion-Merge-Sort的復(fù)雜度O(nK + nlg(n/K)).
還有一個(gè)問題，某個(gè)值K應(yīng)該取多大才算是最合適呢?
當(dāng)K=1時(shí)，Insertion-Merge-Sort就成了Merge-Sort， 當(dāng)K=n時(shí)，Insertion-Merge-Sort就成了Insertion-Sort。理論上，K的取值不應(yīng)該使得Insertion-Merge-Sort的復(fù)雜度高于Merge-Sort的復(fù)雜度即O(nlgn), 如果按這個(gè)要求推理，那么K應(yīng)該屬于O(lgn)。 在實(shí)踐中，K可以取所有Insertion-Sort還比Merge-Sort快的最大值。但是在不同的計(jì)算環(huán)境和不同的輸入下，這個(gè)值也會(huì)不一樣。我們只能根據(jù)實(shí)驗(yàn)的情況取一個(gè)多數(shù)情況下比較好的K值。Java的Arrays.sort(.)函數(shù)取的是7，你可以看JDK的源代碼。好像Java的Arrays類以前用的是Quick-Sort算法, 不知道什么時(shí)候換成Insertion-Merge-Sort了。
本文所有源代碼。
注腳
以上所有的復(fù)雜度實(shí)際上即是上限，也是下限，習(xí)慣上應(yīng)該用Theta表示，而O一般只表示一個(gè)上限，由于Theta不好打，只好這樣了，而且O的知名度要高很多，也被人濫用了很多。具體參照Knuth的論文Big Omicron and big Omega and big Theta。
轉(zhuǎn)載請(qǐng)保留
http://m.tkk7.com/xilaile/archive/2007/04/29/114453.html