一、思想
歸并排序：將一個數組排序，可以先（遞歸地）將它分成兩半部份分別排序，然后將結果歸并起來；
二、概念
歸并：將兩個有序的數組歸并成一個更大的有序數組；
三、特點
優點：能夠保證將任意長度為N的數組排序所需要的時間和NlogN成正比；
缺點：需要額外的空間和N成正比；
四、實現方法
將兩個不同的有序數組歸并到第三個數組中；
先將前半部分排序，在將后半部分排序，然后在數組中移動元素而不需要使用額外的空間；
五、代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
/** * 歸并排序 * * @author pengcx * */public class Merge extends Sort { /** 歸并所需的輔助數組 */ private static Comparable[] aux; public static void main(String[] args) { String[] a = { "d", "a", "w", "b", "q" }; Merge.sort(a); show(a); } public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length - 1); } /** * 排序數組的a[lo]至a[hi]元素 * * @param a * 數組a * @param lo * 最小元素位置lo * @param hi * 最大元素位置hi */ private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) { return; } // 計算數組中間位置 int mid = lo + (hi - lo) / 2; // 排序數組a左邊的元素 sort(a, lo, mid); // 排序數組a右邊的元素 sort(a, mid + 1, hi); // 合并數組a左邊和右邊的元素 merge(a, lo, mid, hi); } /** * 將數組a的a[lo]至a[mid]的元素與a[mid]至a[hi]的元素合并 * * @param a * 合并的數組a * @param lo * 最小數組元素lo * @param mid * 中間元素位置mid * @param hi * 最大元素位置hi */ public static void merge(Comparable[] a, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } for (int k = lo; k <= hi; k++) { // 如果左邊的元素用盡，取右邊的元素 if (i > mid) { a[k] = aux[j++]; } // 如果右邊的元素用盡，取左邊的元素 else if (j > hi) { a[k] = aux[i++]; } // 如果右半邊的當前元素小于左半邊的當前元素，取右半邊元素 else if (less(aux[j], aux[i])) { a[k] = aux[j++]; } // 如果右半邊的當前元素大于等于左半邊的當前元素，取左半邊元素 else { a[k] = aux[i++]; } } } } |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://blog.csdn.net/p106786860/article/details/17750515
