归并排序——C语言描述
0 测试用例框架
1 定义
（1）算法思想：
2路归并：将n个元素的序列不断对半划分成子序列，然后再两两归并有序序列，如此反复，得到有序序列。占空间，效率高，稳定的排序
（2）时间复杂度：
为nlogn。递归深度logn，最底下那层只有1元素，只扫描一次，最上面那层归并所有元素都得扫描一遍，类似等差数列，首项为1， 尾项为n，项数为|logn| + 1，所以时间复杂度为nlogn。
（3）空间复杂度：
为n。最终需要n个元素的空间存相应的数据（不是nlogn，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个元素的大小，所以归并排序的空间复杂度是 O(n)）。
（4）稳定的排序：
因为if (Arr02[Low] <= Arr02[j])的结果不过成功与否肯定会执行下面的语句，不会跳过。
2 代码
void Swap(int *Mem01, int *Mem02) {
int Tmp = *Mem01;
*Mem01 = *Mem02;
*Mem02 = Tmp;
}
/*MergeSort*/
void Merge(int *Arr02, int *Arr01, int Low, int Mid, int High) {
int i, j, k;
for (i = Low, j = Mid + 1; (Low <= Mid) && (j <= High); i++) {
if (Arr02[Low] <= Arr02[j]) {
Arr01[i] = Arr02[Low++];
} else {
Arr01[i] = Arr02[j++];
}
}
if (Low <= Mid) {
for (k = 0; k <= Mid - Low; k++) {
Arr01[i + k] = Arr02[Low + k];
}
}
if (j <= High) {
for (k = 0; k <= High - j; k++) {
Arr01[i + k] = Arr02[j + k];
}
}
}
void MSort(int *Arr, int *Arr01, int Low, int High) {
int Mid;
int Arr02[10];
if (Low == High) {
Arr01[Low] = Arr[High];
} else {
Mid = (Low + High) / 2;
MSort(Arr, Arr02, Low, Mid);
MSort(Arr, Arr02, Mid + 1, High);
Merge(Arr02, Arr01, Low, Mid, High);
}
}
/*MergeSort*/
void MergeSort(int *Arr, int Num) {
if ((Arr == NULL) || (Num <= 1)) {
return;
}
MSort(Arr, Arr, 0, Num - 1);
}
4 测试用例
void TestCmpArr(int *CmpArr, int Num, int *Arr) {
int Index = 0;
int CmpNum = 0;
TestNum++;
for (Index = 0; Index < Num; ++Index) {
if (CmpArr[Index] == Arr[Index]) {
CmpNum++;
}
}
if (CmpNum != Num) {
printf("Incorrect!\n");
FaildNum++;
}
else {
printf("Correct!\n");
PassNum++;
}
}
/*TestMergeSort*/
void TestMergeSort(void) {
/*Test01: Normal*/
int Arr01[] = { 1, 3, 2, 5, 4, 0 };
int Num01 = 6;
int CmpArr01[] = { 0, 1, 2, 3, 4, 5 };
/*Test02: Exist same mem*/
int Arr02[] = { 5, 3, 0, 3, 4};
int Num02 = 5;
int CmpArr02[] = { 0, 3, 3, 4, 5 };
/*Test03: Normal*/
int Arr03[] = { 7, 6, 5, 4, 3, 2, 1, 0 };
int Num03 = 8;
int CmpArr03[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
/*Test04: Two Mem*/
int Arr04[] = { 1, 0 };
int Num04 = 2;
int CmpArr04[] = { 0, 1 };
/*Test05: Only 1 Mem*/
int Arr05[] = { 0 };
int Num05 = 1;
int CmpArr05[] = { 0 };
printf("-------Test start----------\n");
InitNum();
/*Test01*/
printf("\n-------Test 01----------\n");
MergeSort(Arr01, Num01);
PrintArr(Arr01, Num01);
TestCmpArr(CmpArr01, Num01, Arr01);
/*Test02*/
printf("\n-------Test 02----------\n");
MergeSort(Arr02, Num02);
PrintArr(Arr02, Num02);
TestCmpArr(CmpArr02, Num02, Arr02);
/*Test03*/
printf("\n-------Test 03----------\n");
MergeSort(Arr03, Num03);
PrintArr(Arr03, Num03);
TestCmpArr(CmpArr03, Num03, Arr03);
/*Test04*/
printf("\n-------Test 04----------\n");
MergeSort(Arr04, Num04);
PrintArr(Arr04, Num04);
TestCmpArr(CmpArr04, Num04, Arr04);
/*Test05*/
printf("\n-------Test 05----------\n");
MergeSort(Arr05, Num05);
PrintArr(Arr05, Num05);
TestCmpArr(CmpArr05, Num05, Arr05);
/*Test Result*/
printf("\n-------Test result----------\n");
TestResult();
}
打印结果：
-------Test start----------
-------Test 01----------
Arr[0] = 0
Arr[1] = 1
Arr[2] = 2
Arr[3] = 3
Arr[4] = 4
Arr[5] = 5
Correct!
-------Test 02----------
Arr[0] = 0
Arr[1] = 3
Arr[2] = 3
Arr[3] = 4
Arr[4] = 5
Correct!
-------Test 03----------
Arr[0] = 0
Arr[1] = 1
Arr[2] = 2
Arr[3] = 3
Arr[4] = 4
Arr[5] = 5
Arr[6] = 6
Arr[7] = 7
Correct!
-------Test 04----------
Arr[0] = 0
Arr[1] = 1
Correct!
-------Test 05----------
Arr[0] = 0
Correct!
-------Test result----------
Print test result;
TestNum = 5, PassNum = 5, FaildNum = 0