歸并排序是一個典型的基于分治的遞回演算法，它不斷地將原陣列分成大小相等的兩個子陣列（可能相差1），最終當劃分的子陣列大小為1時，將劃分的有序子陣列組合并成一個更大的有序陣列，
演算法分析：
分，也就是把原陣列劃分成兩個子陣列的程序，
治，它將兩個有序陣列合并成一個更大的有序陣列，
它將陣列平均分成兩部分：center=（left+right）/2，當陣列分的足夠小時（陣列中只有一個元素時），只有一個元素的陣列自然而然地就可以視為是有序的，此時就可以進行合并操作了，因此，上面講的合并兩個有序的子陣列，是從只有一個元素的兩個字陣列開始合并的，
合并后的元素個數：從1->2->4->8->...
舉例：
比如初始陣列為：[24，13，25，1，2，27，38，15]
1）分成了兩個大小相等的子陣列：[24，13，25，1]，[2，27，38，15]
2）再劃分成四個大小相等的子陣列：[24，13]，[25，1]，[2，27]，[38，15]
3）此時，left<right還是成立的，再分為：[24]，[13]，[25]，[1]，[2]，[27]，[38]，[15]
此時，有8個小陣列，每個陣列都可以視為有序的陣列！每個陣列中的left=right，從遞回中回傳，故開始執行合并（第21行）：
merge([24],[13])，得到[13,24]
merge([25],[1])，得到[1,25]
......
最終得到有序陣列，
復雜度分析：
歸并排序中，用到了一個臨時陣列，故空間復雜度為O(n)；由歸并排序的遞回公式：T(n)=2T(n/2)+O(n)，可知時間復雜度為O(nlogn)，
歸并排序中的比較次數是所有排序中最少的，原因是，它一開始是不斷地劃分，比較只發生在合并各個有序的子陣列時，
穩定性：
歸并排序是穩定排序，它也是一種十分高效的排序，能利用完全二叉樹特性的排序一般性能都不會太差，Java中Arrays.sort()采用了一種名為TimSort的排序演算法，就是歸并排序的優化版本，從上圖中可以看出，每次合并操作的平均時間復雜度為O(n)，而完全二叉樹的深度為|O(nlogn)|，總的平均時間復雜度為O(nlogn)，而且，歸并排序的最好/最壞平均時間復雜度均為O(nlogn)，
演算法實作：
第一種方法：
1 public class MergeSort {
2 /*
3 * 將一個陣列中的兩個相鄰有序區間合并成一個
4 * 引數說明：
5 * a -- 包含兩個有序區間的陣列
6 * start -- 第1個有序區間的起始地址，
7 * mid -- 第1個有序區間的結束地址，也是第2個有序區間的起始地址，
8 * end -- 第2個有序區間的結束地址，
9 */
10 public static void merge(int[] a, int start, int mid, int end) {
11 int[] tmp = new int[end-start+1]; // tmp是匯總2個有序區的臨時區域
12 int i = start; // 第1個有序區的索引
13 int j = mid + 1; // 第2個有序區的索引
14 int k = 0; // 臨時區域的索引
15 while(i <= mid && j <= end) {
16 if (a[i] <= a[j])
17 tmp[k++] = a[i++];
18 else
19 tmp[k++] = a[j++];
20 }
21
22 while(i <= mid)
23 tmp[k++] = a[i++];
24
25 while(j <= end)
26 tmp[k++] = a[j++];
27
28 // 將排序后的元素，全部都整合到陣列a中，
29 for (i = 0; i < k; i++)
30 a[start + i] = tmp[i];
31
32 tmp=null;
33 }
34
35 /*
36 * 歸并排序(從上往下)
37 *
38 * 引數說明：
39 * a -- 待排序的陣列
40 * start -- 陣列的起始地址
41 * endi -- 陣列的結束地址
42 */
43 public static void mergeSortUp2Down(int[] a, int start, int end) {
44 if(a==null || start >= end)
45 return ;
46
47 int mid = (end + start)/2;
48 mergeSortUp2Down(a, start, mid); // 遞回排序a[start...mid]
49 mergeSortUp2Down(a, mid+1, end); // 遞回排序a[mid+1...end]
50
51 // a[start...mid] 和 a[mid...end]是兩個有序空間，
52 // 將它們排序成一個有序空間a[start...end]
53 merge(a, start, mid, end);
54 }
55
56 /*
57 * 對陣列a做若干次合并：陣列a的總長度為len，將它分為若干個長度為gap的子陣列；
58 * 將"每2個相鄰的子陣列" 進行合并排序，
59 *
60 * 引數說明：
61 * a -- 待排序的陣列
62 * len -- 陣列的長度
63 * gap -- 子陣列的長度
64 */
65 public static void mergeGroups(int[] a, int len, int gap) {
66 int i;
67 int twolen = 2 * gap; // 兩個相鄰的子陣列的長度
68
69 // 將"每2個相鄰的子陣列" 進行合并排序，
70 for(i = 0; i+2*gap-1 < len; i+=(2*gap))
71 merge(a, i, i+gap-1, i+2*gap-1);
72
73 // 若 i+gap-1 < len-1，則剩余一個子陣列沒有配對，
74 // 將該子陣列合并到已排序的陣列中，
75 if ( i+gap-1 < len-1)
76 merge(a, i, i + gap - 1, len - 1);
77 }
78
79 /*
80 * 歸并排序(從下往上)
81 *
82 * 引數說明：
83 * a -- 待排序的陣列
84 */
85 public static void mergeSortDown2Up(int[] a) {
86 if (a==null)
87 return ;
88
89 for(int n = 1; n < a.length; n*=2)
90 mergeGroups(a, a.length, n);
91 }
92
93 public static void main(String[] args) {
94 int i;
95 int a[] = {80,30,60,40,20,10,50,70};
96
97 System.out.printf("before sort:");
98 for (i=0; i<a.length; i++)
99 System.out.printf("%d ", a[i]);
100 System.out.printf("\n");
101 mergeSortUp2Down(a, 0, a.length-1); // 歸并排序(從上往下)
102 //mergeSortDown2Up(a); // 歸并排序(從下往上)
103
104 System.out.printf("after sort:");
105 for (i=0; i<a.length; i++)
106 System.out.printf("%d ", a[i]);
107 System.out.printf("\n");
108 }
109 }
第二種方法：
1 public class MergeSortTest {
2 public static void main(String[] args) {
3 int[] data = https://www.cnblogs.com/HuiH/p/new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
4 print(data);
5 mergeSort(data);
6 System.out.println("排序后的陣列：");
7 print(data);
8 }
9 public static void mergeSort(int[] data) {
10 sort(data, 0, data.length - 1);
11 }
12 public static void sort(int[] data, int left, int right) {
13 if (left >= right)
14 return;
15 // 找出中間索引
16 int center = (left + right) / 2;
17 // 對左邊陣列進行遞回
18 sort(data, left, center);
19 // 對右邊陣列進行遞回
20 sort(data, center + 1, right);
21 // 合并
22 merge(data, left, center, right);
23 print(data);
24 }
25 /**
26 * 將兩個陣列進行歸并，歸并前面 2 個陣列已有序，歸并后依然有序
27 * @param data
28 * 陣列物件
29 * @param left
30 * 左陣列的第一個元素的索引
31 * @param center
32 * 左陣列的最后一個元素的索引，center+1 是右陣列第一個元素的索引
33 * @param right
34 * 右陣列最后一個元素的索引
35 */
36 public static void merge(int[] data, int left, int center, int right) {
37 // 臨時陣列
38 int[] tmpArr = new int[data.length];
39 // 右陣列第一個元素索引
40 int mid = center + 1;
41 // third 記錄臨時陣列的索引
42 int third = left;
43 // 快取左陣列第一個元素的索引
44 int tmp = left;
45 while (left <= center && mid <= right) {
46 // 從兩個陣列中取出最小的放入臨時陣列
47 if (data[left] <= data[mid]) {
48 tmpArr[third++] = data[left++];
49 } else {
50 tmpArr[third++] = data[mid++];
51 }
52 }
53 // 剩余部分依次放入臨時陣列（實際上兩個 while 只會執行其中一個）
54 while (mid <= right) {
55 tmpArr[third++] = data[mid++];
56 }
57 while (left <= center) {
58 tmpArr[third++] = data[left++];
59 }
60 // 將臨時陣列中的內容拷貝回原陣列中
61 // （原 left-right 范圍的內容被復制回原陣列）
62 while (tmp <= right) {
63 data[tmp] = tmpArr[tmp++];
64 }
65 }
66 public static void print(int[] data) {
67 for (int i = 0; i < data.length; i++) {
68 System.out.print(data[i] + "\t");
69 }
70 System.out.println();
71 }
72 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135936.html
標籤：其他
上一篇：資料結構-字串的統計相關操作
下一篇：快速排序演算法