有意思的排序算法合并排序
合并排序也可以用打牌的过程来说明，假设桌面上朝上放着两摞已经排好序的牌，现在要将这两摞已排好序的牌合成一摞，首先，取两摞中位于最上面的两张中最小的一张并将其加入到新的一摞中，然后接着从两摞中再取一张最小的加入到新的一摞中，因为第二张，肯定比第一张要大，因此要加入到第一张的后面才行。
从上面可以看出，合并排序是利用分治法进行排序的算法，直观地操作如下：
分解 ：将n个元素分成各含n/2个元素的子序列；
解决 ：用合并排序法对两个子序列进行递归地排序；
合并 ：合并两个已排序的子序列以得到排序结果。
我就不写伪代码了，直接用Java将其实现的代码如下：
1 /**
2 * 合并两个排好的序列
3 * @param A
4 * int数组
5 * @param p
6 * 起始位置
7 * @param q
8 * 中间位置
9 * @param r
10 * 终止位置
11 * @param isInc
12 * isInc 是否升序，true为升序，false为降序
13 */
14 private void merge( int [] A, int p, int q, int r, boolean isInc) {
15 int nLeft = q - p + 1 ;
16 int nRight = r - q;
17 int [] left = new int [nLeft];
18 int [] right = new int [nRight];
19 int i = 0, j = 0, k = 0 ;
20 for (i = 0; i < nLeft; i++ ) {
21 left[i] = A[p + i];
22 }
23 for (j = 0; j < nRight; j++ ) {
24 right[j] = A[q + j + 1 ];
25 }
26 i = 0 ;
27 j = 0 ;
28 for (k = p; k <= r; k++ ) {
29 if (isInc ^ (left[i] <= right[j])) {
30 A[k] = right[j];
31 j++ ;
32 } else {
33 A[k] = left[i];
34 i++ ;
35 }
36
37 if (i == nLeft) {
38 k++ ;
39 for (; j < nRight; j++ ) {
40 A[k] = right[j];
41 k++ ;
42 }
43 }
44 if (j == nRight) {
45 k++ ;
46 for (; i < nLeft; i++ ) {
47 A[k] = left[i];
48 k++ ;
49 }
50 }
51 }
52 }
1 /**
2 * 合并排序
3 * @param A
4 * int数组
5 * @param p
6 * 起始位置
7 * @param r
8 * 终止位置
9 * @param isInc
10 * 是否升序，true为升序，false为降序
11 */
12 private void mergeSort( int [] A, int p, int r, boolean isInc) {
13 int q = 0 ;
14 if (p < r) {
15 q = (p + r) / 2 ;
16 mergeSort(A, p, q, isInc);
17 mergeSort(A, q + 1 , r, isInc);
18 merge(A, p, q, r, isInc);
19 }
20 }
合并排序不是原地进行排序的，时间复杂度为O(nlgn)。
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did49218