c语言排序之归并排序(递归和非递归)

下面我来为你详细讲解“C语言排序之归并排序（递归和非递归）”的完整攻略：

什么是归并排序

归并排序是一种基于分治策略的排序算法，其基本思想是将原始数据分成若干个小的子序列，然后将这些小的子序列两两合并成为较大的子序列，直到最终合并成为完整的有序序列。

归并排序可以采用递归和非递归两种方式实现。

归并排序递归实现

归并排序的递归实现相对容易理解，可以通过以下步骤进行实现：

1. 把待排序的序列不断二分，直到每个子序列只有一个元素。
2. 将相邻的子序列进行合并，得到有序的子序列，重复此过程，直到合并成为完整的有序序列。

下面是归并排序的递归实现的示例代码：

void merge_sort(int arr[], int left, int right)
{
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);      // 对左边进行排序
        merge_sort(arr, mid + 1, right); // 对右边进行排序
        merge(arr, left, mid, right);   // 合并左右两个有序序列
    }
}

其中 merge 函数用于合并两个有序序列，具体如下：

void merge(int arr[], int left, int mid, int right)
{
    int i = left, j = mid + 1, k = 0;
    int temp[right - left + 1];

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left, k = 0; i <= right; i++, k++) {
        arr[i] = temp[k];
    }
}

该函数的功能是将 arr 数组中从下标 left 到 mid 和从下标 mid+1 到 right 的两个有序子数组合并为一个有序数组。

归并排序非递归实现

归并排序的非递归实现是通过迭代的方式实现的，它使用二路归并策略将原序列不断划分成有序的子序列，并不断地进行合并，直到合并成为完整的有序序列。

下面是归并排序的非递归实现的示例代码：

void merge_sort(int arr[], int len)
{
    int left, mid, right;

    for (int step = 1; step < len; step <<= 1) {
        left = 0;

        while (left + step < len) {
            mid = left + step - 1;  // 左子序列的最后一个元素
            right = mid + step < len ? mid + step : len - 1;  // 右子序列的最后一个元素
            merge(arr, left, mid, right);  // 合并两个有序子序列
            left = right + 1;  // 移动左指针到下一个合并区间的起点
        }   
    }
}

其中 step 指的是分治进行合并的步长，每次将原序列划分为若干个长为 step 的子序列进行两两合并。

示例说明

下面是一个示例数组：

int arr[] = {8, 3, 9, 4, 1, 2, 7, 5};
int len = sizeof(arr) / sizeof(arr[0]);

对这个数组使用归并排序进行排序，可以选择递归实现或非递归实现。

递归实现

使用归并排序的递归实现对数组进行排序，可以使用以下代码：

merge_sort(arr, 0, len-1);

排序后，该数组的元素变为：1 2 3 4 5 7 8 9。

非递归实现

使用归并排序的非递归实现对数组进行排序，可以使用以下代码：

merge_sort(arr, len);

排序后，该数组的元素变为：1 2 3 4 5 7 8 9。

至此，归并排序的递归和非递归两种实现方式都已经讲解完毕。