八大排序之归并排序

目录

一、思想

思路演绎

二、代码

三、运行结果

四、时间复杂度和空间复杂度

1.时间复杂度

2.空间复杂度

3.稳定性

---

一、思想

• 将两段有序的数据合并成一段更有序的数据
• 也叫做二路归并

思路演绎

1.1个数据作为一段

2.两段内进行比较，小数据的先放在新段内。

3.上述12步骤为一次归并，实现了一次段内有序

4.定义变量：L1,L2,H1,H2，标记下标

5.总是比较L1和L2，小的优先进入新段内。比较完一次，“4”进入新段内执行L1++，“5”进入新段内执行L2++，“7”进行新段内执行L1++，“9”进入新段内L2++。此时L1，L2的位置均越界，L1和L2位置均重新定义，如下图所示：

第二次归并结果如下：

如上所示，进行多次归并直至一个段，即可完成排序。

二、代码

//归并排序
//一次归并
static void Merge(int* arr, int len, int gap)//gap：长度
{
    /*越界分析：
    *low1,high1肯定不会越界，因为最大和为字符串总长度
    *low2=high1+1即便越界了,也进入不到while (low2 < len)循环内，只会出现在1个归并段的情况
    *high2用三目运算符约束，防止越界
    */
    int low1=0;
    int high1=low1+gap-1;//gap-1！！
    int low2=high1+1 ;//写成这样不行：low2 = high1 + 1< len - 1 ? high1 + 2 : len - 1;没办法约束high2
    int high2 = low2 + gap - 1 < len - 1 ? low2 + gap - 1:len-1;
    int* brr = (int*)malloc(len * sizeof(int));//开辟新数组
    assert(brr != NULL);
    int i = 0;
    //有两个归并段
    //l2存在就证明有2个归并段；l2=len-1：有2个归并段
    while (low2 < len)//high2
    {
        //两个归并段都还有数据，需要比较
        while (low1<=high1&&low2<=high2)
        {
            //总是比较l1,l2的值，小的放到brr内
            if (arr[low1] <= arr[low2])
            {
                brr[i++] = arr[low1++];
            }
            else
                brr[i++] = arr[low2++];
        }
        //一个归并段的数据已经完成了，另一个还有数据,多出的数据直接放到合并段
        while (low1 <= high1)//第1段是长的那一段，还没结束
        {
            brr[i++] = arr[low1++];
        }
        while (low2 <= high2)//第2段是长的那一段，还没结束
        {
            brr[i++] = arr[low2++];
        }
        //下两个归并段,变量往后走
        /*越界分析：
        * high1越不越界无所谓，即便越界，那low2肯定越界，还是一样进不到下一趟循环内
        *low2:在while(low2
        *high2用三目运算符约束，防止越界
        */
        low1 = high2 + 1;
        high1 = low1 + gap - 1;
        low2 = high1 + 1;
        high2 = low2 + gap < len ? low2 + gap - 1 : len - 1;
    }
    //只有一个归并段
    while (low1 < len)//low2>len即只有1个归并段
    {
        brr[i++] = arr[low1++];
    }
    //将归并好的数据拷贝到arr中
    for (int i = 0; i < len; i++)
    {
        arr[i] = brr[i];
    }
    free(brr);
}
void MergrSort(int* arr, int len)
{
    for (int i = 1; i < len; i *= 2)
    {
        Merge(arr, len, i);
    }
}
void Show(int* arr,int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
}
int main()
{
    int arr[] = { 6,4 ,7,8,10,-5,90,34,55};
    Show(arr,sizeof(arr) / sizeof(arr[0])); 
    printf("\n ");
    MergrSort(arr, sizeof(arr) / sizeof(arr[0]));
    Show(arr, sizeof(arr) / sizeof(arr[0]));
}
 
 

三、运行结果

四、时间复杂度和空间复杂度

1.时间复杂度

•                 一次归并：O(n)
•                 一次划分：O(n)
•                 归并排序：O(nlogn)

2.空间复杂度

•                 O(n)  //申请了新数组

3.稳定性

•                 稳定