一、个人理解
实现归并排序，分两步：
1、合并两个有序数组。
2、分治法将无序数组拆分成一个个小的有序数组，再进行排序。
二、实现思路
（1）合并两个有序数组
给两个有序数组，两个数组a,b分别从第一位开始比较，这里以升序为例,可以分为三种情况：
1、a的元素大于b的元素，将b的元素放入新的数组中，且b的索引位进一，a的索引位不变。
2、a的元素小于b的元素，将a的元素放入新的数组中，且a的索引位进一，b的索引位不变。
3、a的元素等于b的元素，将a,b的元素放入新的数组中，且a,b的索引位都进一。
我们还需要思索一下，如果两个数组的长度不相等，是不是就会出现一个数组遍历完了，另一个还没有遍历完，所以在上面的比较结束后，也就是说有一个数组已遍历完，我们只需要另一个数组的剩余元素全部复制到新数组中就OK啦！！！
（2）分治法
这里是为了让归并排序适用于无序数组，我们可以把一个数组从中间一分为二，看左边的数组和右边的数组是否有序，如果是无序的就继续拆分，当两个数组中分别都只有一个元素时，一定是有序的，是不是又想到了递归的思想，对头，递归分为两步，结束标志：数组中只有一个元素时，退出。规则逻辑：数组从中间拆分，将左边的数组和右边的数组分别排序，再将两个数组合并，是不是有一些想法了，希望对大家有帮助！！！
三、实现函数介绍
（1）MergeUnOrderedArray函数：
适用范围：
适用于无序和有序数组。
| 参数名称 | 描述 |
|---|---|
| Array | 整型数组。 |
| L | 数组的起始位置索引号。 |
| R | 数组的结束位置索引号。 |
（2）MergeArray函数：
适用范围：
数组例如：{4,5,6,1,2,3}，
要求数组中是以一个分割点切割后是两个有序的数组。
| 参数名称 | 描述 |
|---|---|
| Array | 整型数组。 |
| TopPointIndex | 数组的起始位置索引号。 |
| BreakPointIndex | 分割点的索引号，以上面的数组为例，数值1的索引位3为传入参数。 |
| EndPointIndex | 某后一个元素的索引位，以上面的数组为例，数值3的索引位5为传入参数。 |
（3）Merge2SortArray函数：
适用范围：
要求传入两个有序数组，都正序或都倒序。
数组1例如：{4,5,6}
数组2例如：{1,2,3}
| 参数名称 | 描述 |
|---|---|
| Array1 | 整型数组。 |
| ArraySize1 | Array1长度。 |
| Array2 | 整型数组。 |
| ArraySize2 | Array2长度。 |
四、代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
实现归并排序，分两步：
1、合并两个有序数组。
2、分治法将无序数组拆分成一个个小的有序数组，再进行排序。
*/
void PrintArray(int Array[], int ArraySize);
void MergeArray(int Array[], int TopPointIndex, int BreakPointIndex, int EndPointIndex);
int* Merge2SortArray(int Array1[], int ArraySize1, int Array2[], int ArraySize2);
void MergeUnOrderedArray(int Array[], int L, int R);
int main()
{
//测试Merge2SortArray函数
printf("+++++++++++++++++++++++++++++++\n");
printf("测试Merge2SortArray函数:\n");
int Array1[] = { 1,2,3,4,5,6 };
int Array2[] = { 1,7,8,9 };
int ArraySize1 = sizeof(Array1) / sizeof(int);
int ArraySize2 = sizeof(Array2) / sizeof(int);
PrintArray(Merge2SortArray(Array1, ArraySize1, Array2, ArraySize2), ArraySize1 + ArraySize2);
//测试MergeArray函数
printf("+++++++++++++++++++++++++++++++\n");
printf("测试MergeArray函数:\n");
int ArraySize = ArraySize1 + ArraySize2;
int* Array = (int*)malloc(sizeof(int) * ArraySize);
int i = 0;
int j = 0;
int x = 0;
while (i < ArraySize1)
{
Array[x] = Array1[i];
x++;
i++;
}
while (j < ArraySize2)
{
Array[x] = Array2[j];
x++;
j++;
}
//int Array[] = { 6,7,8,9,1,2,3,4,5,6 };
//PrintArray(Array, ArraySize);
MergeArray(Array, 0, ArraySize1, ArraySize - 1);
PrintArray(Array, ArraySize);
free(Array);
//测试MergeUnOrderedArray函数
printf("+++++++++++++++++++++++++++++++\n");
printf("测试MergeUnOrderedArray函数:\n");
int TestArray[] = { 2,3,5,1,4,5,6,7,9,8 };
int TestArraySize = sizeof(TestArray) / sizeof(int);
//printf("%d\n",TestArraySize);
PrintArray(TestArray, TestArraySize);
MergeUnOrderedArray(TestArray, 0, TestArraySize - 1);
PrintArray(TestArray, TestArraySize);
return 0;
}
/*
MergeUnOrderedArray函数：
适用范围：
适用于无序和有序数组。
参数：
参数Array：整型数组。
参数L：数组的起始位置索引号。
参数R：数组的结束位置索引号。
*/
void MergeUnOrderedArray(int Array[], int L, int R)
{
if (L == R)
{
return;
}
else
{
int M = (L + R) / 2;
MergeUnOrderedArray(Array, L, M);
MergeUnOrderedArray(Array, M + 1, R);
MergeArray(Array, L, M + 1, R);
}
}
/*
MergeArray函数：
适用范围：
数组例如：{4,5,6,1,2,3}，
要求数组中是以一个分割点切割后是两个有序的数组。
参数：
参数Array：整型数组。
参数TopPointIndex：数组的起始位置索引号。
参数BreakPointIndex：分割点的索引号，以上面的数组为例，数值1的索引位3为传入参数。
参数EndPointIndex：某后一个元素的索引位，以上面的数组为例，数值3的索引位5为传入参数。
*/
void MergeArray(int Array[], int TopPointIndex, int BreakPointIndex, int EndPointIndex)
{
if (Array == NULL)
{
return;
}
int ArraySize1 = BreakPointIndex - TopPointIndex;
int ArraySize2 = EndPointIndex - BreakPointIndex + 1;
int* Array1 = (int*)malloc(sizeof(int) * ArraySize1);
int* Array2 = (int*)malloc(sizeof(int) * ArraySize2);
int i, j;
int x;
//初始化两个数组
for (x = TopPointIndex, i = 0; i < ArraySize1; i++, x++)
{
Array1[i] = Array[x];
}
for (j = 0; j < ArraySize2; j++, x++)
{
Array2[j] = Array[x];
}
//PrintArray(Array1, ArraySize1);
//PrintArray(Array2, ArraySize2);
memcpy(Array + TopPointIndex, Merge2SortArray(Array1, ArraySize1, Array2, ArraySize2), sizeof(int) * (ArraySize1 + ArraySize2));
//i指向ResArray
//j指向Array
//int* ResArray = Merge2SortArray(Array1, ArraySize1, Array2, ArraySize2);
//for ( i = 0,j = TopPointIndex; i < (ArraySize1 + ArraySize2); i++,j++)
//{
// Array[j] = ResArray[i];
//}
free(Array1);
free(Array2);
}
/*
Merge2SortArray函数：
适用范围：
要求传入两个有序数组，都正序或都倒序。
数组1例如：{4,5,6}
数组2例如：{1,2,3}
参数：
参数Array1：整型数组。
参数ArraySize1：Array1长度。
参数Array2：整型数组。
参数ArraySize2：Array2长度。
*/
int* Merge2SortArray(int Array1[], int ArraySize1, int Array2[], int ArraySize2)
{
//printf("###########################\n");
//printf("Array1 : ");
//PrintArray(Array1, ArraySize1);
//printf("Array2 : ");
//PrintArray(Array2, ArraySize2);
if (Array1 == NULL || Array2 == NULL)
{
return NULL;
}
int* ResArray = (int*)malloc(sizeof(int) * (ArraySize1 + ArraySize2));
int i = 0;
int j = 0;
int x = 0;
//i指向Array1的起始位置。
//j指向Array2的起始位置。
//x指向ResArray的起始位置。
while ((i < ArraySize1) && (j < ArraySize2))
{
if (Array1[i] < Array2[j])
{
ResArray[x] = Array1[i];
x++;
i++;
}
else if (Array1[i] > Array2[j])
{
ResArray[x] = Array2[j];
x++;
j++;
}
else //数组元素相等
{
ResArray[x] = Array2[j];
x++;
ResArray[x] = Array1[i];
x++;
j++;
i++;
}
}
//如果数组的元素没有全部循环完，跳入此循环。
while (i < ArraySize1)
{
ResArray[x] = Array1[i];
x++;
i++;
}
while (j < ArraySize2)
{
ResArray[x] = Array2[j];
x++;
j++;
}
//printf("ResArray : ");
//PrintArray(ResArray, ArraySize2 + ArraySize1);
return ResArray;
}
void PrintArray(int Array[], int ArraySize)
{
int i;
for (i = 0; i < ArraySize; i++)
{
printf("%d ", Array[i]);
}
printf("\n");
}
五、测试结果
C:\Users\czg>C:\Users\czg\source\repos\x64\Debug\C_TEST.exe
+++++++++++++++++++++++++++++++
测试Merge2SortArray函数:
1 1 2 3 4 5 6 7 8 9
+++++++++++++++++++++++++++++++
测试MergeArray函数:
1 1 2 3 4 5 6 7 8 9
+++++++++++++++++++++++++++++++
测试MergeUnOrderedArray函数:
2 3 5 1 4 5 6 7 9 8
1 2 3 4 5 5 6 7 8 9
