02归并排序——分治递归

02_归并排序_——分治_递归_

#include <stdio.h>

void merge(int arr[], int l, int m, int r)
{
    int n1 = m -l + 1;
    int n2 = r -m;
    
    //创建临时数组
    int L[n1], R[n2];
    
    for(int i = 0; i < n1; i++)
    {
        L[i] = arr[l + i];
    }
    for(int j = 0; j < n2; j++)
    {
        R[j] = arr[m + 1 + j];
    }
    
    int i = 0, j = 0, k = l;
    while(i < n1 && j < n2)
    {
        if(L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while(i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
    while(j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if(l < r)
    {
        int m = l + (r - 1) / 2;
        
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        mergeSort(arr, l, m, r);
    }
}

void printArrary(int arr[], int size)
{
    for(i = 0; i < sieze; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main()
{
    int arr[] ={12, 11, 10, 5, 6, 3};
    int arr_sieze = sizeof(arr) / siezeof(arr[0]);
    
    printf("排序前的数组:\n");
    printArray(arr, arr_size);
    
    mergeSort(arr, 0, arr_size - 1);
    
    printf("排序后的数组:\n");
    printArray(arr, arr_size);
    
    return 0;
}

notion

递归

递归指的是一个函数直接或间接调用自身。递归通常用于解决可以分解为子问题的复杂问题,每个子问题的结构与原问题相似

  1. 基准情况:

    这是递归函数的终止条件,当满足这个条件时,递归停止,直接返回结果

  2. 递归情况:

    这是递归函数调用自身的地方,将问题分解成一个或多个子问题,然后递归地解决这些子问题

从栈的角度分析递归
第一次调用:

入栈

  1. mergeSort(arr, 0, 5) 被调用
  2. l = 0, r = 5, 计算中间点 m = 2
  3. 入栈 mergeSort(arr, 0, 2) 和mergeSort(arr, 3, 5)

出栈

  1. 等待 mergeSort(arr, 0, 2)mergeSort(arr, 3, 5) 完成

  2. 合并 merge(arr, 0, 2, 5)

第二次调用(左半部分)

入栈

  • mergeSort(arr, 0, 2) 被调用。
  • l = 0, r = 2, 计算中间点 m = 1
  • 入栈 mergeSort(arr, 0, 1)mergeSort(arr, 2, 2)

出栈

  • 等待 mergeSort(arr, 0, 1)mergeSort(arr, 2, 2) 完成。
  • 合并 merge(arr, 0, 1, 2)
第三次调用(左半部分的左半部分)

入栈

  • mergeSort(arr, 0, 1) 被调用。
  • l = 0, r = 1, 计算中间点 m = 0
  • 入栈 mergeSort(arr, 0, 0)mergeSort(arr, 1, 1)

出栈

  • 等待 mergeSort(arr, 0, 0)mergeSort(arr, 1, 1) 完成。
  • 合并 merge(arr, 0, 0, 1)
基准情况

入栈

  • mergeSort(arr, 0, 0) 被调用。
  • l = 0, r = 0,满足基准情况,直接返回。
  • 入栈 mergeSort(arr, 1, 1) 被调用。
  • l = 1, r = 1,满足基准情况,直接返回。

出栈

  • mergeSort(arr, 0, 0)mergeSort(arr, 1, 1) 返回后,合并 merge(arr, 0, 0, 1)
  • mergeSort(arr, 0, 1) 返回。

从栈的角度分析,不断的入栈,规模不断减小,等待基准条件满足再回归(出栈),最高回归出结果

分治

过将一个复杂问题分解为较小的子问题,逐个解决这些子问题,然后合并解决方案来解决原问题。归并排序是分治法的典型例子。分治法的主要步骤包括:

  1. 分解(Divide):将原问题分解成若干个规模较小但形式与原问题相同的子问题
  2. 解决(Conquer):递归地解决这些子问题。当子问题规模足够小时(达到基准情况),直接解决
  3. 合并(Combine):将子问题的解决方案合并成原问题的解决方案
归并中的分治
分解

在归并排序中,数组arr[1…r] 被分解成两个数组:

左半部分:arr[l…m]

右半部分:arr[m+1…r]

其中,m 是中间点,计算公式为:m = l + (r - l) / 2

解决

对于每个子数组,递归地调用 mergeSort,继续将其分解成更小的子数组,直到每个子数组只包含一个元素或为空(达到基准情况),这时不需要进一步分解,直接返回

合并

当递归返回时,子数组已经有序,然后调用merge函数,将两个有序的子数组合并成一个有序的数组

归并排序的分治过程eg

假设我们有一个数组 arr = {12, 11, 13, 5, 6, 7},我们调用 mergeSort(arr, 0, 5)

  1. 初始数组arr = {12, 11, 13, 5, 6, 7}
  2. 第一次分解
    • 左半部分:{12, 11, 13}
    • 右半部分:{5, 6, 7}
  3. 继续分解左半部分
    • {12, 11, 13} -> {12, 11}{13}
    • {12, 11} -> {12}{11}
  4. 基准情况
    • {12}{11} 不再分解,直接返回。
  5. 合并左半部分
    • 合并 {12}{11} -> {11, 12}
    • 合并 {11, 12}{13} -> {11, 12, 13}
  6. 继续分解右半部分
    • {5, 6, 7} -> {5, 6}{7}
    • {5, 6} -> {5}{6}
  7. 基准情况
    • {5}{6} 不再分解,直接返回。
  8. 合并右半部分
    • 合并 {5}{6} -> {5, 6}
    • 合并 {5, 6}{7} -> {5, 6, 7}
  9. 最终合并
    • 合并 {11, 12, 13}{5, 6, 7} -> {5, 6, 7, 11, 12, 13}

最终,数组被排序为 {5, 6, 7, 11, 12, 13}

在这里插入图片描述

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

相关推荐

  1. 归并排序(实现)

    2024-07-09 17:44:03       6 阅读

最近更新

  1. matlab中feval()的用法

    2024-07-09 17:44:03       0 阅读
  2. 【Linux常用命令】之mkdir命令

    2024-07-09 17:44:03       0 阅读
  3. 在 macOS 上使用 Jadx 进行 APK 反编译

    2024-07-09 17:44:03       0 阅读
  4. C++生成随机数的两种方法

    2024-07-09 17:44:03       0 阅读
  5. Blazor Webassembly多标签页实现非iframe的实现

    2024-07-09 17:44:03       0 阅读
  6. Lianwei 安全周报|2024.07.22

    2024-07-09 17:44:03       0 阅读

热门阅读

  1. 算法刷题1-10大排序算法汇总

    2024-07-09 17:44:03       11 阅读
  2. 设计模式——工厂模式

    2024-07-09 17:44:03       10 阅读
  3. c语言中printf函数参数个数可变实现原理

    2024-07-09 17:44:03       7 阅读
  4. FFmpeg——视频拼接总结

    2024-07-09 17:44:03       8 阅读
  5. php框架详解-symfony框架

    2024-07-09 17:44:03       10 阅读
  6. 红黑树,B+树,B树的结构原理及对比

    2024-07-09 17:44:03       6 阅读
  7. 代码随想录算法训练营:21/60

    2024-07-09 17:44:03       9 阅读
  8. Vue3 对于内嵌Iframe组件进行缓存

    2024-07-09 17:44:03       5 阅读