【排序算法】归并排序（C语言）

【���序算法】—— 归并排序（C语言）

目录

• 一、归并排序的原理
• 二、两个有序数组排序和合并
• • 1. 原地排序
  • 2. 创建临时空间
  • 二、递归实现
  • 三、非递归实现
  • • 1. 实现思路
    • 2. 数组边界问题
    • 3. 代码实现

      一、归并排序的原理

      归并排序（MergeSort） 是建立在归并操作上的一种有效的排序算法，采用分治法排序，分为分解、合并两个步骤。

      分解：将数组分割成两个数组，再分别将两个数组又细分成2个数组，直到，最后每个数组都是一个元素，这时将该单元素数组看为有序数组

      合并：将分割的有序数组进行排序，排成有序数组后继续为上一个分割它的数组合并，直到数组被合并成原来的数组，此时已经排好序了

      二、两个有序数组排序和合并

      1. 原地排序

      从头到尾遍历，选最小值放前面

      1. 合并的两个数组是一个数组分割开的，所以它们的首尾是相连的，用箭头i指向合并后数组的当前下标位置
      1. 将2和1比较，1小，所以将1赋值给合并后数组的第一个元素，此时我们发现，数组arr1的首元素被覆盖，所以不能直接赋值
      1. 若是将arr1的元素向后挪动一格，则数据正常，但是效率太低，不可取

      从后往前遍历，选最大值放后面

      1. 用箭头i指向合并后数组的后边，从后往前遍历
      1. 8比7大，赋值给i指向的位置，此时7被覆盖，不行
      1. 若是将7和8交换呢，看样子可以，那如果是如下数组就不行了，arr1的有序性被破坏，不能继续这样排序了

      2. 创建临时空间

      1. 既然无法原地排序，那我们创建临时空间，对两个有序数组排序
      1. 从前往后遍历，选出最小值放在temp数组前面部分
      1. 直到排序完成，将temp数组中的数据拷贝回原数组，arr1和arr2就合并成为有序数组arr

      二、递归实现

      我们使用递归来实现数组的分割和合并，它的逻辑非常像二叉树的后序遍历，由于我们要使用递归，又要申请临时空间，所以我们先申请好临时空间，再将归并排序过程作为子函数调用，这样不用在每次递归过程申请释放空间

      归并排序调用递归

      void MergeSort(int* arr, int size){int* temp = (int*)malloc(size * sizeof(int));if (temp == NULL){perror("malloc fail\n");return;}_MergeSort(arr, 0, size - 1, temp);//归并排序的过程free(temp);temp = NULL;}

      归并排序

      由于我们递归过程中要用区间来分割函数，所以参数为待排数组的闭区间，使代码书写更加方便，这也是将递归过程单独调用的好处

      void _MergeSort(int* arr, int left, int right, int* temp){    //分解：    //分割数组只有一个元素时停止递归if (left >= right){return;}int mid = (left + right) / 2;_MergeSort(arr, left, mid, temp);//分割并排序数组左半边_MergeSort(arr, mid + 1, right, temp);//分割并排序数组右半边    //合并：int begin1 = left, end1 = mid;//数组1的左右区间int begin2 = mid + 1, end2 = right;//数组2的左右区间int i = begin1;    //排序两个有序数组while (begin1 if (arr[begin1] temp[i] = arr[begin1];begin1++;}else{temp[i] = arr[begin2];begin2++;}i++;}while (begin1 temp[i] = arr[begin1];begin1++;i++;}while (begin2 temp[i] = arr[begin2];begin2++;i++;}//拷贝临时数组的内容到原数组（可以调用memcpy函数）//memcpy(arr+left, temp+left, (right-left+1)*sizeof(int));for (i = left; i arr[i] = temp[i];}}    //申请空间    int* temp = (int*)malloc(size * sizeof(int));    if (temp == NULL)    {        perror("malloc fail!\n");        return;    }        //归并排序    int gap = 1;    while (gap