Insertion-Sort和Merge-Sort是两种非常有代表性的排序算法。Insertion-Sort逐个将未排序的元素插入到正确的位置,下面这张图很形象的描述了Insertion-Sort.
所以Insertion-Sort也是一种incremental的算法。Merge-Sort采用一种完全不同的方式,即是divide-and-conquer, 将元素分成两组,先分别将这两组排好序,然后再组合起来,就如下图所示,
Java实现
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(n2), 而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.
约需32分钟,如果你有兴趣可以在你的电脑上试试看,所有的源代码和测试程序可以在下面下载。
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 * K2=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。
转载请保留
http://www.blogjava.net/xilaile/archive/2007/04/29/114453.html