這次我學(xué)的是合并排序。合并排序的主要思想是：把兩個(gè)已經(jīng)排序好的序列進(jìn)行合并，成為一個(gè)排序好的
序列。例如：13579 2468這兩個(gè)序列，各自都是排好序的，然后我們進(jìn)行合并，成為123456789這樣一個(gè)
排好序的序列。貌似這個(gè)跟排序關(guān)系不大，因?yàn)榕判蚪o的是一個(gè)亂的序列，而合并是合并的兩個(gè)已經(jīng)排序
好的序列。且慢，我們可以把需要排序的數(shù)據(jù)分解成N個(gè)子序列，當(dāng)分解的子序列所包含數(shù)據(jù)個(gè)數(shù)為1的時(shí)
候，那么這個(gè)序列不久是有序了嗎？然后再合并。這個(gè)就是有名的”分治“了。。（哈哈。沒有想到這么
好的思想能在這里學(xué)到。）。例如321分成3，2，1三個(gè)序列，1這個(gè)序列是有序的啦。（只有一個(gè)數(shù)據(jù)當(dāng)
然是有序的啦。當(dāng)我傻的啊。哈哈）。同理2，3都是有序的。然后我們逐一的合并他們。3，2合并為23，
然后在23與1合并為123。哈哈，排序成功。合并排序主要思路就是這樣了。
但是，問題又出來了，怎么合并兩個(gè)有序列呢？我相信我應(yīng)該理解了數(shù)組的存儲方式，所以直接用數(shù)組說
事啦。。我們先把下標(biāo)定位到各有序子序列的開始，也把合并之后數(shù)組的下標(biāo)定位到最初。那么下標(biāo)對應(yīng)
的位置就是他們當(dāng)前的最小值了。然后拿他們來比較，把更小的那個(gè)放到合并之后數(shù)組的下標(biāo)位置。這樣
，合并后數(shù)組的第一個(gè)元素就是他們的最小值了。接著，控制合并后數(shù)組的下標(biāo)后移一個(gè)，把比較時(shí)小數(shù)
字所在序列對應(yīng)的下標(biāo)后移一個(gè)。這樣。下次比較的時(shí)候，他得到就是他的第二小，（第一下已經(jīng)合并了
）就是當(dāng)前最小值了，在于另一個(gè)序列的當(dāng)前最小值比較，用小的一個(gè)放到合并后數(shù)組的相應(yīng)位置。依次
類推。接著當(dāng)數(shù)據(jù)都合并玩了結(jié)束，合并完成。（這樣說忒空泛了，云里霧里的，BS一下以前的我。）
1357 2468 來做例子：
(1回合) 1357 2468 00000(合并后數(shù)據(jù)空)
(2) 357 2468 100000(0表示空) 因?yàn)? < 2所以把1放到合并后位置中了（這里1并不是丟掉了，而是下
標(biāo)變?yōu)橹赶?了，1是沒有寫而已。呵呵。理解為數(shù)組的下標(biāo)指向了3）
(3) 357 468 120000 因?yàn)? > 2，所以把而放進(jìn)去
(4) 57 468 123000 同理3 < 4
(5) 57 68 1234000 同理5 > 4
(6) 7 68 1234500 同理5 > 6
(7) 7 8 1234560 同理7 > 6
(8) 0(空了) 8 12345670 同理7 < 8
(9) 0 0 12345678 弄最后一個(gè)
PS:這是用記事本寫的哈，沒有錢買office而且也不是很會用。哈哈。我想以后的我也不見怪的哈。。關(guān)
鍵還有書嘛，這里看不懂還有教科書。。
當(dāng)然，這些只是思路。并不是一定一成不變的這樣。合并OK，那么我們就可以用合并排序了哦！哈哈。。
不過注意，那個(gè)321全部弄成一個(gè)單個(gè)數(shù)字，然后一個(gè)一個(gè)合并這樣來合并似乎不是很好，貌似還有更好
的解決方案。哈哈，對了，就是我先分一半來合并。如果這一半是排好序的，那么合并不久簡單了嗎？但
是我怎么讓一般排好序呢。呵呵簡單，我一半在分一半合并排序，在分一半合并排序，直到分到兩個(gè)都是
1個(gè)了，就合并，ok!
例如，81726354：
(1)分成9172 6354
(2)把8172 分成 81 和72 把6354分成63和54
(3)81分成8和1,哦能合并了哦。合并為18, 同理72，63，54，也可以分解成單個(gè)合并為27,36,45
(4) 現(xiàn)在變?yōu)榱?18, 27, 36, 45了，這個(gè)時(shí)侯，18 和27能合并了，合并為1278 同理36,合并為45 3456
(5) 好了最好吧，1278和3456合并為12345678.ok排序成功。哈哈。
這樣把一個(gè)問題分解為兩個(gè)或多個(gè)小問題，然后在分解，最后解決小小問題，已達(dá)到解決打問題的目的。
哈哈。分治很強(qiáng)大。哈哈。如果看不懂，我也沒有辦法啦。。看教科書吧。呵呵
思路主要就是這樣了哦：
程序?qū)崿F(xiàn)上也有點(diǎn)技巧。這個(gè)就不說了，直接奉上源代碼：
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 //合并排序的合并程序他合并數(shù)組nData中位置為[nP,nM) 和[nM,nR).這個(gè)是更接近標(biāo)準(zhǔn)的思路
5 bool MergeStandard(int nData[], int nP, int nM, int nR)
6 {
7 int n1 = nM - nP; //第一個(gè)合并數(shù)據(jù)的長度
8 int n2 = nR - nM; //第二個(gè)合并數(shù)據(jù)的長度
9
10 int *pnD1 = new int[n1 + 1]; //申請一個(gè)保存第一個(gè)數(shù)據(jù)的空間
11 int *pnD2 = new int[n2 + 1]; //申請二個(gè)保存第一個(gè)數(shù)據(jù)的空間
12
13 for (int i = 0; i < n1; ++i) //復(fù)制第一個(gè)數(shù)據(jù)到臨時(shí)空間里面
14 {
15 pnD1[i] = nData[nP + i];
16 }
17 pnD1[n1] = INT_MAX; //將最后一個(gè)數(shù)據(jù)設(shè)置為最大值(哨兵)
18
19 for (int i = 0; i < n2; ++i) //復(fù)制第二個(gè)數(shù)據(jù)到臨時(shí)空間里面
20 {
21 pnD2[i] = nData[nM + i];
22 }
23 pnD2[n2] = INT_MAX; //將最后一個(gè)數(shù)據(jù)設(shè)置為最大值(哨兵)
24
25 n1 = n2 = 0;
26
27 while(nP < nR)
28 {
29 nData[nP++] = pnD1[n1] < pnD2[n2] ? pnD1[n1++] : pnD2[n2++]; //取出當(dāng)前最小值到指定位置
30 }
31
32 delete pnD1;
33 delete pnD2;
34 return true;
35 }
36
37 //合并排序的合并程序他合并數(shù)組nData中位置為[nP,nM) 和[nM,nR).
38 bool Merge(int nData[], int nP, int nM, int nR)
39 {
40 //這里面有幾個(gè)注釋語句是因?yàn)楫?dāng)時(shí)想少寫幾行而至?？此贫塘耍鋵?shí)運(yùn)行時(shí)間是一樣的，而且不易閱讀。
41
42 int nLen1 = nM - nP; //第一個(gè)合并數(shù)據(jù)的長度
43 int nLen2 = nR - nM; //第二個(gè)合并數(shù)據(jù)的長度
44 int* pnD1 = new int[nLen1]; //申請一個(gè)保存第一個(gè)數(shù)據(jù)的空間
45 int* pnD2 = new int[nLen2]; //申請一個(gè)保存第一個(gè)數(shù)據(jù)的空間
46
47 int i = 0;
48 for ( i = 0; i < nLen1; ++i) //復(fù)制第一個(gè)數(shù)據(jù)到臨時(shí)空間里面
49 {
50 pnD1[i] = nData[nP + i];
51 }
52
53 int j = 0;
54 for (j = 0; j < nLen2; ++j) //復(fù)制第二個(gè)數(shù)據(jù)到臨時(shí)空間里面
55 {
56 pnD2[j] = nData[nM + j];
57 }
58
59 i = j = 0;
60 while (i < nLen1 && j < nLen2)
61 {
62 //nData[nP++] = pnD1[i] < pnD2[j] ? pnD1[i++] : pnD2[j++]; //取出當(dāng)前最小值添加到數(shù)據(jù)中
63
64 if (pnD1[i] < pnD2[j]) //取出最小值，并添加到指定位置中，如果pnD1[i] < pnD2[j]
65 {
66 nData[nP] = pnD1[i]; //取出pnD1的值，然后i++，定位到下一個(gè)個(gè)最小值。
67 ++i;
68 }
69 else //這里同上
70 {
71 nData[nP] = pnD2[j];
72 ++j;
73 }
74 ++nP; //最后np++，到確定下一個(gè)數(shù)據(jù)
75 }
76
77 if (i < nLen1) //如果第一個(gè)數(shù)據(jù)沒有結(jié)束（第二個(gè)數(shù)據(jù)已經(jīng)結(jié)束了）
78 {
79 while (nP < nR) //直接把第一個(gè)剩余的數(shù)據(jù)加到nData的后面即可。
80 {
81 //nData[nP++] = pnD1[i++];
82 nData[nP] = pnD1[i];
83 ++nP;
84 ++i;
85 }
86 }
87 else //否則（第一個(gè)結(jié)束，第二個(gè)沒有結(jié)束）
88 {
89 while (nP < nR) //直接把第一個(gè)剩余的數(shù)據(jù)加到nData的后面即可。
90 {
91 //nData[nP++] = pnD2[j++];
92 nData[nP] = pnD2[j];
93 ++nP;
94 ++j;
95 }
96 }
97
98 delete pnD1; //釋放申請的內(nèi)存空間
99 delete pnD2;
100
101 return true;
102 }
103
104 //合并的遞歸調(diào)用,排序[nBegin, nEnd)區(qū)間的內(nèi)容
105 bool MergeRecursion(int nData[], int nBegin, int nEnd)
106 {
107 if (nBegin >= nEnd - 1) //已經(jīng)到最小顆粒了,直接返回
108 {
109 return false;
110 }
111
112 int nMid = (nBegin + nEnd) / 2; //計(jì)算出他們的中間位置，便于分治
113 MergeRecursion(nData, nBegin, nMid); //遞歸調(diào)用，合并排序好左邊一半
114 MergeRecursion(nData, nMid, nEnd); //遞歸調(diào)用，合并排序好右邊一半
115 //Merge(nData, nBegin, nMid, nEnd); //將已經(jīng)合并排序好的左右數(shù)據(jù)合并，時(shí)整個(gè)數(shù)據(jù)排序完成
116 MergeStandard(nData, nBegin, nMid, nEnd);//(用更接近標(biāo)準(zhǔn)的方法合并)
117
118 return true;
119 }
120
121 //合并排序
122 bool MergeSort(int nData[], int nNum)
123 {
124 return MergeRecursion(nData, 0, nNum); //調(diào)用遞歸，完成合并排序
125 }
126
127 int main()
128 {
129 int nData[10] = {4,10,3,8,5,6,7,4,9,2}; //創(chuàng)建10個(gè)數(shù)據(jù)，測試
130
131 MergeSort(nData, 10);
132 for (int i = 0; i < 10; ++i)
133 {
134 printf("%d ", nData[i]);
135 }
136
137 printf("\n");
138 system("pause");
139 return 0;
140 }
141