归并排序递归法和非递归法的简单简单介绍

基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序核心步骤：先将数组分组，往下分直到分为1个数据，然后开始合并，两两合并，合并的时候先比较两组数据中的数据的大小，按顺序依次合并到临时数组temp中，然后再将合并到temp数组中有序的数据覆盖到原数组中。

#include <stdio.h>
// 归并排序
// 时间复杂度O(N*logN)
// 空间复杂度O(N)
void _MergeSort(int* arr, int left, int right, int* temp)
{if (left >= right)return;// 递归划分区间，直到区间内只有一个数据后开始归并int mid = (left + right) / 2;// [left,mid] [mid+1,right]_MergeSort(arr, left, mid, temp);_MergeSort(arr, mid+1, right, temp);// 归并[left,mid] [mid+1,right]有序,归并到temp了int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])temp[index++] = arr[begin1++];elsetemp[index++] = arr[begin2++];}// 可能有一段没结束，具体那一段不知道，只有一个循环可以进入while(begin1<=end1)temp[index++] = arr[begin1++];while (begin2 <= end2)temp[index++] = arr[begin2++];// 将归并后在temp的数据拷贝回原数组for (int i = left;i <= right; i++){arr[i] = temp[i];}
}// 归并排序
void MergeSort(int* arr, int n)
{assert(arr);int* temp = malloc(sizeof(int) * n);// 传入闭区间【0，n-1】_MergeSort(arr, 0, n - 1, temp);free(temp);
}void TestMergeSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };MergeSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}void TestMergeSortNonR()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };MergeSortNonR(arr,sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{//TestInsertSort();//TestShellSort();//TestSelectSort();//TestBubbleSort();//TestHeapSort();//TestQuickSort();TestMergeSort();TestMergeSortNonR();return 0;
}

函数的递归实现图：

非递归法

从上面的递归图可以看出，合并的时候是2个数据开始合并，也就是区间【0，0】和【1，1】合并，【2，2】和【3，3】合并；然后【0，1】和【2，3】合并到这里时是两个数据两个数据之间合并，依次类推。那么非递归方法，需要控制好合并的下标即可。

// 归并排序--非递归方法
void MergeArry(int* arr, int begin1, int end1, int begin2, int end2, int* temp)
{int left = begin1, right = end2;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])temp[index++] = arr[begin1++];elsetemp[index++] = arr[begin2++];}// 可能有一段没结束，具体那一段不知道while (begin1 <= end1)temp[index++] = arr[begin1++];while (begin2 <= end2)temp[index++] = arr[begin2++];// 将归并后在temp的数据拷贝回原数组for (int i = left;i <= right; i++){arr[i] = temp[i];}
}void MergeSortNonR(int* arr, int n)
{assert(arr);int* temp = malloc(sizeof(int) * n);int gap = 1;  // 控制几个数据的合并排序while (gap < n){for (int i = 0;i < n;i += 2 * gap){// 归并+排序的区间（数组长度不是2的次方数时第二组可能会越界访问）// [i,i+gap-1] [i+gap,i+2*gap-1]int begin1 = i, end1 = i + gap - 1;    // 第一组int begin2 = i + gap, end2 = i + 2 * gap - 1;  // 第二组// 1、合并时只有第一组if (begin2 >= n)break;// 2、合并时第二组只有部分数据，需要修正边界if (end2 >= n)end2 = n - 1; // 只有一个数值的时候，直接让end2=最后一个数值就行了MergeArry(arr, begin1, end1, begin2, end2, temp);}Printarry(arr, n);gap *= 2;}free(temp);
}

实现图：

结论：

归并排序是一种基于分治思想的有效排序算法，其核心是通过递归将数组不断二分直至单个元素，然后按顺序合并有序子序列。算法分为递归和非递归两种实现方式：递归法通过_MergeSort函数划分区间并调用自身，然后将有序子序列合并到临时数组后回写；非递归法使用MergeSortNonR函数，通过gap变量控制合并步长，逐步扩大有序区间。两种方法都使用MergeArry函数进行具体合并操作，时间复杂度均为O(N*logN)，空间复杂度为O(N)。代码示例展示了完整的实现过程，包括边界处理和数据拷贝等关键步骤。