您的位置:首页 > 文旅 > 美景 > 02归并排序——分治递归

02归并排序——分治递归

2024/12/23 15:40:26 来源:https://blog.csdn.net/qq_44348970/article/details/140137634  浏览:    关键词: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}

在这里插入图片描述

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com