C语言学习-20-归并排序

一、个人理解

实现归并排序，分两步：
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