递归法与非递归法的实现与对比

递归法实现

递归排序法通过不断将数组划分为较小的子数组并进行归并，最终得到有序数组。其核心思想是将问题分解，解决子问题后再合并结果。如图所示，递归排序法通过递归划分数组并进行归并，最终得到有序数组。

实现代码

void Merge(int *arr, int begin, int mid, int end, int *temp) {    int begin1 = begin, end1 = mid;    int begin2 = mid + 1, end2 = end;    int sub = begin;    while (begin1 <= end1 && begin2 <= end2) {        if (arr[begin1] <= arr[begin2])            temp[sub++] = arr[begin1++];        else            temp[sub++] = arr[begin2++];    }    if (begin1 <= end1)        memcpy(temp + sub, arr + begin1, sizeof(int) * (end1 - begin1 + 1));    if (begin2 <= end2)        memcpy(temp + sub, arr + begin2, sizeof(int) * (end2 - begin2 + 1));    memcpy(arr + begin, temp + begin, sizeof(int) * (end - begin + 1));}void MergeR(int *arr, int begin, int end, int *temp) {    if (begin >= end)        return;    int mid = begin + (end - begin) / 2;    MergeR(arr, begin, mid, temp);    MergeR(arr, mid + 1, end, temp);    Merge(arr, begin, mid, end, temp);}void MergeSort(int *arr, int begin, int end, int size) {    assert(arr);    int *temp = (int *)malloc(sizeof(int) * size);    MergeR(arr, begin, end, temp);    free(temp);}

非递归实现方法

非递归实现的基本思想与递归方法类似，但实现方式不同。非递归算法通过循环来模拟递归的分解与合并过程。具体而言，我们需要定义一个变量来控制合并的步伐，并严格控制边界条件。

实现代码

void _Merge(int *arr, int begin1, int end1, int begin2, int end2, int *temp) {    int _begin1 = begin1;    int sub = begin1;    while (begin1 <= end1 && begin2 <= end2) {        if (arr[begin1] <= arr[begin2])            temp[sub++] = arr[begin1++];        else            temp[sub++] = arr[begin2++];    }    if (begin1 <= end1)        memcpy(temp + sub, arr + begin1, sizeof(int) * (end1 - begin1 + 1));    if (begin2 <= end2)        memcpy(temp + sub, arr + begin2, sizeof(int) * (end2 - begin2 + 1));    memcpy(arr + _begin1, temp + _begin1, sizeof(int) * (end2 - _begin1 + 1));}void MergeSortNoR(int *arr, int size) {    assert(arr);    int *temp = (int *)malloc(sizeof(int) * size);    int gap = 1;    while (gap < size) {        for (int i = 0; i < size; i += gap) {            int end1 = i + gap - 1;            int begin2 = i + gap;            int end2 = begin2 + gap - 1;            if (end2 >= size)                end2 = size - 1;            _Merge(arr, i, end1, begin2, end2, temp);        }        gap *= 2;    }    free(temp);}

特性

递归排序法和非递归排序法在时间复杂度和空间复杂度上都有其独特之处。通过对比两种方法，可以更好地理解其优缺点。

转载地址：http://hmse.baihongyu.com/

你可能感兴趣的文章