|
歸并排序介紹
將兩個(gè)的有序數(shù)列合并成一個(gè)有序數(shù)列，我們稱之為"歸并"。歸并排序(Merge Sort)就是利用歸并思想對(duì)數(shù)列進(jìn)行排序。根據(jù)具體的實(shí)現(xiàn)，歸并排序包括"從上往下"和"從下往上"2種方式。
1. 從下往上的歸并排序：將待排序的數(shù)列分成若干個(gè)長度為1的子數(shù)列，然后將這些數(shù)列兩兩合并；得到若干個(gè)長度為2的有序數(shù)列，再將這些數(shù)列兩兩合并；得到若干個(gè)長度為4的有序數(shù)列，再將它們兩兩合并；直接合并成一個(gè)數(shù)列為止。這樣就得到了我們想要的排序結(jié)果。(參考下面的圖片)
2. 從上往下的歸并排序：它與"從下往上"在排序上是反方向的。它基本包括3步：
① 分解 -- 將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn) mid = (low + high)/2;
② 求解 -- 遞歸地對(duì)兩個(gè)子區(qū)間a[low...mid] 和 a[mid+1...high]進(jìn)行歸并排序。遞歸的終結(jié)條件是子區(qū)間長度為1。
③ 合并 -- 將已排序的兩個(gè)子區(qū)間a[low...mid]和 a[mid+1...high]歸并為一個(gè)有序的區(qū)間a[low...high]。
下面的圖片很清晰的反映了"從下往上"和"從上往下"的歸并排序的區(qū)別。
歸并排序圖文說明
歸并排序(從上往下)代碼
/*
* 將一個(gè)數(shù)組中的兩個(gè)相鄰有序區(qū)間合并成一個(gè)
*
* 參數(shù)說明：
* a -- 包含兩個(gè)有序區(qū)間的數(shù)組
* start -- 第1個(gè)有序區(qū)間的起始地址。
* mid -- 第1個(gè)有序區(qū)間的結(jié)束地址。也是第2個(gè)有序區(qū)間的起始地址。
* end -- 第2個(gè)有序區(qū)間的結(jié)束地址。
*/
void merge(int a[], int start, int mid, int end)
{
int *tmp = (int *)malloc((end-start+1)*sizeof(int)); // tmp是匯總2個(gè)有序區(qū)的臨時(shí)區(qū)域
int i = start; // 第1個(gè)有序區(qū)的索引
int j = mid + 1; // 第2個(gè)有序區(qū)的索引
int k = 0; // 臨時(shí)區(qū)域的索引
while(i <= mid && j <= end)
{
if (a[i] <= a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while(i <= mid)
tmp[k++] = a[i++];
while(j <= end)
tmp[k++] = a[j++];
// 將排序后的元素，全部都整合到數(shù)組a中。
for (i = 0; i < k; i++)
a[start + i] = tmp[i];
free(tmp);
}
/*
* 歸并排序(從上往下)
*
* 參數(shù)說明：
* a -- 待排序的數(shù)組
* start -- 數(shù)組的起始地址
* endi -- 數(shù)組的結(jié)束地址
*/
void merge_sort_up2down(int a[], int start, int end)
{
if(a==NULL || start >= end)
return ;
int mid = (end + start)/2;
merge_sort_up2down(a, start, mid); // 遞歸排序a[start...mid]
merge_sort_up2down(a, mid+1, end); // 遞歸排序a[mid+1...end]
// a[start...mid] 和 a[mid...end]是兩個(gè)有序空間，
// 將它們排序成一個(gè)有序空間a[start...end]
merge(a, start, mid, end);
}
從上往下的歸并排序采用了遞歸的方式實(shí)現(xiàn)。它的原理非常簡單，如下圖：
通過"從上往下的歸并排序"來對(duì)數(shù)組{80,30,60,40,20,10,50,70}進(jìn)行排序時(shí)：
1. 將數(shù)組{80,30,60,40,20,10,50,70}看作由兩個(gè)有序的子數(shù)組{80,30,60,40}和{20,10,50,70}組成。對(duì)兩個(gè)有序子樹組進(jìn)行排序即可。
2. 將子數(shù)組{80,30,60,40}看作由兩個(gè)有序的子數(shù)組{80,30}和{60,40}組成。
將子數(shù)組{20,10,50,70}看作由兩個(gè)有序的子數(shù)組{20,10}和{50,70}組成。
3. 將子數(shù)組{80,30}看作由兩個(gè)有序的子數(shù)組{80}和{30}組成。
將子數(shù)組{60,40}看作由兩個(gè)有序的子數(shù)組{60}和{40}組成。
將子數(shù)組{20,10}看作由兩個(gè)有序的子數(shù)組{20}和{10}組成。
將子數(shù)組{50,70}看作由兩個(gè)有序的子數(shù)組{50}和{70}組成。
歸并排序(從下往上)代碼
/*
* 對(duì)數(shù)組a做若干次合并：數(shù)組a的總長度為len，將它分為若干個(gè)長度為gap的子數(shù)組；
* 將"每2個(gè)相鄰的子數(shù)組" 進(jìn)行合并排序。
*
* 參數(shù)說明：
* a -- 待排序的數(shù)組
* len -- 數(shù)組的長度
* gap -- 子數(shù)組的長度
*/
void merge_groups(int a[], int len, int gap)
{
int i;
int twolen = 2 * gap; // 兩個(gè)相鄰的子數(shù)組的長度
// 將"每2個(gè)相鄰的子數(shù)組" 進(jìn)行合并排序。
for(i = 0; i+2*gap-1 < len; i+=(2*gap))
{
merge(a, i, i+gap-1, i+2*gap-1);
}
// 若 i+gap-1 < len-1，則剩余一個(gè)子數(shù)組沒有配對(duì)。
// 將該子數(shù)組合并到已排序的數(shù)組中。
if ( i+gap-1 < len-1)
{
merge(a, i, i + gap - 1, len - 1);
}
}
/*
* 歸并排序(從下往上)
*
* 參數(shù)說明：
* a -- 待排序的數(shù)組
* len -- 數(shù)組的長度
*/
void merge_sort_down2up(int a[], int len)
{
int n;
if (a==NULL || len<=0)
return ;
for(n = 1; n < len; n*=2)
merge_groups(a, len, n);
}
從下往上的歸并排序的思想正好與"從下往上的歸并排序"相反。如下圖：
通過"從下往上的歸并排序"來對(duì)數(shù)組{80,30,60,40,20,10,50,70}進(jìn)行排序時(shí)：
1. 將數(shù)組{80,30,60,40,20,10,50,70}看作由8個(gè)有序的子數(shù)組{80},{30},{60},{40},{20},{10},{50}和{70}組成。
2. 將這8個(gè)有序的子數(shù)列兩兩合并。得到4個(gè)有序的子樹列{30,80},{40,60},{10,20}和{50,70}。
3. 將這4個(gè)有序的子數(shù)列兩兩合并。得到2個(gè)有序的子樹列{30,40,60,80}和{10,20,50,70}。
4. 將這2個(gè)有序的子數(shù)列兩兩合并。得到1個(gè)有序的子樹列{10,20,30,40,50,60,70,80}。
歸并排序的時(shí)間復(fù)雜度和穩(wěn)定性
歸并排序時(shí)間復(fù)雜度
歸并排序的時(shí)間復(fù)雜度是O(N*lgN)。
假設(shè)被排序的數(shù)列中有N個(gè)數(shù)。遍歷一趟的時(shí)間復(fù)雜度是O(N)，需要遍歷多少次呢？
歸并排序的形式就是一棵二叉樹，它需要遍歷的次數(shù)就是二叉樹的深度，而根據(jù)完全二叉樹的可以得出它的時(shí)間復(fù)雜度是O(N*lgN)。
歸并排序穩(wěn)定性
歸并排序是穩(wěn)定的算法，它滿足穩(wěn)定算法的定義。
算法穩(wěn)定性 -- 假設(shè)在數(shù)列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。則這個(gè)排序算法是穩(wěn)定的！
歸并排序?qū)崿F(xiàn)
下面給出歸并排序的三種實(shí)現(xiàn)：C、C++和Java。這三種實(shí)現(xiàn)的原理和輸出結(jié)果都是一樣的，每一種實(shí)現(xiàn)中都包括了"從上往下的歸并排序"和"從下往上的歸并排序"這2種形式。
歸并排序C實(shí)現(xiàn)
實(shí)現(xiàn)代碼(merge_sort.c)
1 /**
2 * 歸并排序：C 語言
3 *
4 * @author skywang
5 * @date 2014/03/12
6 */
7
8 #include
9 #include
10
11 // 數(shù)組長度
12 #define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
13
14 /*
15 * 將一個(gè)數(shù)組中的兩個(gè)相鄰有序區(qū)間合并成一個(gè)
16 *
17 * 參數(shù)說明：
18 * a -- 包含兩個(gè)有序區(qū)間的數(shù)組
19 * start -- 第1個(gè)有序區(qū)間的起始地址。
20 * mid -- 第1個(gè)有序區(qū)間的結(jié)束地址。也是第2個(gè)有序區(qū)間的起始地址。
21 * end -- 第2個(gè)有序區(qū)間的結(jié)束地址。
22 */
23 void merge(int a[], int start, int mid, int end)
24 {
25 int *tmp = (int *)malloc((end-start+1)*sizeof(int)); // tmp是匯總2個(gè)有序區(qū)的臨時(shí)區(qū)域
26 int i = start; // 第1個(gè)有序區(qū)的索引
27 int j = mid + 1; // 第2個(gè)有序區(qū)的索引
28 int k = 0; // 臨時(shí)區(qū)域的索引
29
30 while(i <= mid && j <= end)
31 {
32 if (a[i] <= a[j])
33 tmp[k++] = a[i++];
34 else
35 tmp[k++] = a[j++];
36 }
37
38 while(i <= mid)
39 tmp[k++] = a[i++];
40
41 while(j <= end)
42 tmp[k++] = a[j++];
43
44 // 將排序后的元素，全部都整合到數(shù)組a中。
45 for (i = 0; i < k; i++)
46 a[start + i] = tmp[i];
47
48 free(tmp);
49 }
50
51 /*
52 * 歸并排序(從上往下)
53 *
54 * 參數(shù)說明：
55 * a -- 待排序的數(shù)組
56 * start -- 數(shù)組的起始地址
57 * endi -- 數(shù)組的結(jié)束地址
58 */
59 void merge_sort_up2down(int a[], int start, int end)
60 {
61 if(a==NULL || start >= end)
62 return ;
63
64 int mid = (end + start)/2;
65 merge_sort_up2down(a, start, mid); // 遞歸排序a[start...mid]
66 merge_sort_up2down(a, mid+1, end); // 遞歸排序a[mid+1...end]
67
68 // a[start...mid] 和 a[mid...end]是兩個(gè)有序空間，
69 // 將它們排序成一個(gè)有序空間a[start...end]
70 merge(a, start, mid, end);
71 }
72
73
74 /*
75 * 對(duì)數(shù)組a做若干次合并：數(shù)組a的總長度為len，將它分為若干個(gè)長度為gap的子數(shù)組；
76 * 將"每2個(gè)相鄰的子數(shù)組" 進(jìn)行合并排序。
77 *
78 * 參數(shù)說明：
79 * a -- 待排序的數(shù)組
80 * len -- 數(shù)組的長度
81 * gap -- 子數(shù)組的長度
82 */
83 void merge_groups(int a[], int len, int gap)
84 {
85 int i;
86 int twolen = 2 * gap; // 兩個(gè)相鄰的子數(shù)組的長度
87
88 // 將"每2個(gè)相鄰的子數(shù)組" 進(jìn)行合并排序。
89 for(i = 0; i+2*gap-1 < len; i+=(2*gap))
90 {
91 merge(a, i, i+gap-1, i+2*gap-1);
92 }
93
94 // 若 i+gap-1 < len-1，則剩余一個(gè)子數(shù)組沒有配對(duì)。
95 // 將該子數(shù)組合并到已排序的數(shù)組中。
96 if ( i+gap-1 < len-1)
97 {
98 merge(a, i, i + gap - 1, len - 1);
99 }
100 }
101
102 /*
103 * 歸并排序(從下往上)
104 *
105 * 參數(shù)說明：
106 * a -- 待排序的數(shù)組
107 * len -- 數(shù)組的長度
108 */
109 void merge_sort_down2up(int a[], int len)
110 {
111 int n;
112
113 if (a==NULL || len<=0)
114 return ;
115
116 for(n = 1; n < len; n*=2)
117 merge_groups(a, len, n);
118 }
119
120 void main()
121 {
122 int i;
123 int a[] = {80,30,60,40,20,10,50,70};
124 int ilen = LENGTH(a);
125
126 printf("before sort:");
127 for (i=0; i)
128 printf("%d ", a[i]);
129 printf("\n");
130
131 merge_sort_up2down(a, 0, ilen-1); // 歸并排序(從上往下)
132 //merge_sort_down2up(a, ilen); // 歸并排序(從下往上)
133
134 printf("after sort:");
135 for (i=0; i)
136 printf("%d ", a[i]);
137 printf("\n");
138 }
歸并排序C++實(shí)現(xiàn)
實(shí)現(xiàn)代碼(MergeSort.cpp) 1 /**
2 * 歸并排序：C++
3 *
4 * @author skywang
5 * @date 2014/03/12
6 */
7
8 #include
9 using namespace std;
10
11 /*
12 * 將一個(gè)數(shù)組中的兩個(gè)相鄰有序區(qū)間合并成一個(gè)
13 *
14 * 參數(shù)說明：
15 * a -- 包含兩個(gè)有序區(qū)間的數(shù)組
16 * start -- 第1個(gè)有序區(qū)間的起始地址。
17 * mid -- 第1個(gè)有序區(qū)間的結(jié)束地址。也是第2個(gè)有序區(qū)間的起始地址。
18 * end -- 第2個(gè)有序區(qū)間的結(jié)束地址。
19 */
20 void merge(int* a, int start, int mid, int end)
21 {
22 int *tmp = new int[end-start+1]; // tmp是匯總2個(gè)有序區(qū)的臨時(shí)區(qū)域
23 int i = start; // 第1個(gè)有序區(qū)的索引
24 int j = mid + 1; // 第2個(gè)有序區(qū)的索引
25 int k = 0; // 臨時(shí)區(qū)域的索引
26
27 while(i <= mid && j <= end)
28 {
29 if (a[i] <= a[j])
30 tmp[k++] = a[i++];
31 else
32 tmp[k++] = a[j++];
33 }
34
35 while(i <= mid)
36 tmp[k++] = a[i++];
37
38 while(j <= end)
39 tmp[k++] = a[j++];
40
41 // 將排序后的元素，全部都整合到數(shù)組a中。
42 for (i = 0; i < k; i++)
43 a[start + i] = tmp[i];
44
45 delete[] tmp;
46 }
47
48 /*
49 * 歸并排序(從上往下)
50 *
51 * 參數(shù)說明：
52 * a -- 待排序的數(shù)組
53 * start -- 數(shù)組的起始地址
54 * endi -- 數(shù)組的結(jié)束地址
55 */
56 void mergeSortUp2Down(int* a, int start, int end)
57 {
58 if(a==NULL || start >= end)
59 return ;
60
61 int mid = (end + start)/2;
62 mergeSortUp2Down(a, start, mid); // 遞歸排序a[start...mid]
63 mergeSortUp2Down(a, mid+1, end); // 遞歸排序a[mid+1...end]
64
65 // a[start...mid] 和 a[mid...end]是兩個(gè)有序空間，
66 // 將它們排序成一個(gè)有序空間a[start...end]
67 merge(a, start, mid, end);
68 }
69
70
71 /*
72 * 對(duì)數(shù)組a做若干次合并：數(shù)組a的總長度為len，將它分為若干個(gè)長度為gap的子數(shù)組；
73 * 將"每2個(gè)相鄰的子數(shù)組" 進(jìn)行合并排序。
74 *
75 * 參數(shù)說明：
76 * a -- 待排序的數(shù)組
77 * len -- 數(shù)組的長度
78 * gap -- 子數(shù)組的長度
79 */
80 void mergeGroups(int* a, int len, int gap)
81 {
82 int i;
83 int twolen = 2 * gap; // 兩個(gè)相鄰的子數(shù)組的長度
84
85 // 將"每2個(gè)相鄰的子數(shù)組" 進(jìn)行合并排序。
86 for(i = 0; i+2*gap-1 < len; i+=(2*gap))
87 {
88 merge(a, i, i+gap-1, i+2*gap-1);
89 }
90
91 // 若 i+gap-1 < len-1，則剩余一個(gè)子數(shù)組沒有配對(duì)。
92 // 將該子數(shù)組合并到已排序的數(shù)組中。
93 if ( i+gap-1 < len-1)
94 {
95 merge(a, i, i + gap - 1, len - 1);
96 }
97 }
98
99 /*
100 * 歸并排序(從下往上)
101 *
102 * 參數(shù)說明：
103 * a -- 待排序的數(shù)組
104 * len -- 數(shù)組的長度
105 */
106 void mergeSortDown2Up(int* a, int len)
107 {
108 int n;
109
110 if (a==NULL || len<=0)
111 return ;
112
113 for(n = 1; n < len; n*=2)
114 mergeGroups(a, len, n);
115 }
116
117 int main()
118 {
119 int i;
120 int a[] = {80,30,60,40,20,10,50,70};
121 int ilen = (sizeof(a)) / (sizeof(a[0]));
122
123 cout << "before sort:";
124 for (i=0; i)
125 cout << a[i] << " ";
126 cout << endl;
127
128 mergeSortUp2Down(a, 0, ilen-1); // 歸并排序(從上往下)
129 //mergeSortDown2Up(a, ilen); // 歸并排序(從下往上)
130
131 cout << "after sort:";
132 for (i=0; i)
133 cout << a[i] << " ";
134 cout << endl;
135
136 return 0;
137 } 上面3種實(shí)現(xiàn)的原理和輸出結(jié)果都是一樣的。下面是它們的輸出結(jié)果：
before sort:80 30 60 40 20 10 50 70
after sort:10 20 30 40 50 60 70 80
|
