[已解决]关于C++归并排序的递归算法

122Ml

已知以下代码：

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

我不太看得懂此算法的思路，求大佬具体解释。

以及请问其中

 while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];

三个while的作用是什么？

以及请问

arr[k] = reg[k];

的作用是什么？

最佳答案

月排行榜 / 总排行榜

isdkz

2023-9-21 14:06:17

这是一种经典的归并排序算法，主要思想是将数组分成两部分，对每一部分递归地进行排序，最后将两个有序的子序列合并成一个有序的序列。这个算法的时间复杂度为O(nlogn)。下面我来详细解释一下代码实现。

merge_sort函数是归并排序的主函数，它调用了merge_sort_recursive函数。merge_sort_recursive函数是递归实现的，它将数组分成两部分，对每一部分递归地进行排序，最后将两个有序的子序列合并成一个有序的序列。

在merge_sort_recursive函数中，首先判断start和end的大小关系，如果start>=end，说明数组只有一个元素或者没有元素，已经有序了，直接返回。否则，计算出中间位置mid，将数组分成两部分[start,mid]和[mid+1,end]，对这两部分分别进行递归排序。

在递归排序完成之后，将两个有序的子序列合并成一个有序的序列。这个过程中需要借助一个辅助数组reg。首先，将两个子序列的起始位置分别记为start1和start2，将两个子序列的结束位置分别记为end1和end2。然后，比较两个子序列的第一个元素，将较小的元素放入reg数组中，并将对应的指针后移一位，直到其中一个指针超出了对应的结束位置。最后，将剩余的元素依次放入reg数组中。

最后，将reg数组中的元素复制到原数组arr中，完成排序。

至于你提到的三个while循环，第一个while循环是将两个子序列合并到reg数组中，第二个和第三个while循环是将剩余的元素放入reg数组中。

而arr[k] = reg[k]的作用是将排序后的数组从辅助数组reg中复制回原数组arr中，以便于下一次的排序。

希望这个解释能够帮到你。

跳转到最佳答案楼层

isdkz

这是一种经典的归并排序算法，主要思想是将数组分成两部分，对每一部分递归地进行排序，最后将两个有序的子序列合并成一个有序的序列。这个算法的时间复杂度为O(nlogn)。下面我来详细解释一下代码实现。

merge_sort函数是归并排序的主函数，它调用了merge_sort_recursive函数。merge_sort_recursive函数是递归实现的，它将数组分成两部分，对每一部分递归地进行排序，最后将两个有序的子序列合并成一个有序的序列。

在merge_sort_recursive函数中，首先判断start和end的大小关系，如果start>=end，说明数组只有一个元素或者没有元素，已经有序了，直接返回。否则，计算出中间位置mid，将数组分成两部分[start,mid]和[mid+1,end]，对这两部分分别进行递归排序。

在递归排序完成之后，将两个有序的子序列合并成一个有序的序列。这个过程中需要借助一个辅助数组reg。首先，将两个子序列的起始位置分别记为start1和start2，将两个子序列的结束位置分别记为end1和end2。然后，比较两个子序列的第一个元素，将较小的元素放入reg数组中，并将对应的指针后移一位，直到其中一个指针超出了对应的结束位置。最后，将剩余的元素依次放入reg数组中。

最后，将reg数组中的元素复制到原数组arr中，完成排序。

至于你提到的三个while循环，第一个while循环是将两个子序列合并到reg数组中，第二个和第三个while循环是将剩余的元素放入reg数组中。

而arr[k] = reg[k]的作用是将排序后的数组从辅助数组reg中复制回原数组arr中，以便于下一次的排序。

希望这个解释能够帮到你。

122Ml

isdkz 发表于 2023-9-21 14:06
这是一种经典的归并排序算法，主要思想是将数组分成两部分，对每一部分递归地进行排序，最后将两个有序的子 ...

请问

reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]

的运算顺序是怎样的？