2017/2/26 使用模板改寫鼠渺，不支持char(char的結(jié)束符需要額外的改變)
合并排序的思想
對(duì)于一個(gè)需要排序的數(shù)組A[0n-1]勋颖，合并排序?qū)⑺环譃槎篈[0[n/2]-1],A[[n/2]~n-1],并對(duì)每一個(gè)子數(shù)組遞歸排序，然后把這兩個(gè)排好序的子數(shù)組合并為一個(gè)有序數(shù)組
偽代碼
- MergeSort,將數(shù)組遞歸拆分并使用Merge排序
MergeSort(A[0~n-1])
//遞歸調(diào)用mergesort對(duì)數(shù)組A[0~n-1]排序
//輸入：一個(gè)可排序數(shù)組A[0~n-1]
//輸出：非降序排列的數(shù)組A[0~n-1]
if(n>1)
copy A[0~[n/2]-1] to B[0~[n/2]-1]
copy A[[n/2]~n-1] to C[0~[(n+1)/2]-1]//向上取整，請(qǐng)思考n為奇數(shù)的情況
MergeSort(B[0~[n/2]-1])
MergeSort(C[0~[(n+1)/2]-1])
Merge(B,C,A)
```
2. Merge，真正實(shí)現(xiàn)排序的函數(shù)
Merge(B[0~p-1],C[0~q-1],A[0~p+q-1])
將兩個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組
//輸入：兩個(gè)有序數(shù)組B[0~p-1],C[0~q-1]
//輸出：A[0~p+q-1]已經(jīng)有序存放B和C中的元素
i=0,j=0,k=0;
while i<p and j<q do
if B[i]<=C[j]
A[k]=B[i];i++;
else
A[k]=C[j];j++;
k++;
if i==p
copy C[j~q-1] to A[k~p+q-1]
else
copy B[i~q-1] to A[k~p+q-1]
#### 分析
1. MergeSort可以結(jié)合下圖理解并思考n=2時(shí)的情況
2. Merge很好理解，因?yàn)锽粪摘，C都是有序數(shù)組瀑晒，從B，C的下標(biāo)i=0,j=0開始徘意，找出兩個(gè)中較小的一個(gè)苔悦，加入到A，并移動(dòng)相應(yīng)的i或j到下一位置映砖，如果其中一個(gè)數(shù)組已經(jīng)計(jì)算完畢间坐，將另一個(gè)數(shù)組的剩余元素直接復(fù)制到A的尾部。
#### 代碼
```c++
#include <iostream>
using namespace std;
void Merge(int *B, int p, int *C, int q, int *A);
void MergeSort(int *A, const int n);
int main()
{
const int n = 8;
int A[n] = {2,5,7,4,3,1,8,9};
MergeSort(A, n);
for (int i = 0; i < n; i++)
cout << A[i] << "\t";
system("pause");
return 0;
}
void MergeSort(int *A, const int n)
{
if (n>1)
{
int nB = n / 2;//向下取正
int nC = (n + 1) / 2;//取上取整
int *B = new int[nB];
int *C = new int[nC];
memcpy(B, A, nB * sizeof(int));
memcpy(C, A + nB, nC * sizeof(int));
MergeSort(B, nB);
MergeSort(C, nC);
Merge(B, nB, C, nC, A);
}
}
void Merge(int *B, int p, int *C, int q, int *A)
{
int i, j, k;
i = j = k = 0;
while (i < p&&j < q)
{
/*由A分配給B的元素肯定在分配給C的元素之前邑退，
當(dāng)B[i]==C[j]應(yīng)該選擇B中的元素竹宋，確保穩(wěn)定性。*/
if (B[i] > C[j])
A[k++] = C[j++];
else
A[k++] = B[i++];
}
if (i == p)//B已到盡頭
memcpy(A + k, C + j, (q - j) * sizeof(int));
else
memcpy(A + k, B + i, (p - i) * sizeof(int));
free(B);
free(C);
}
運(yùn)行結(jié)果
結(jié)果
