关于C++归并排序的递归算法
已知以下代码：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 = arr < arr ? arr : arr;
while (start1 <= end1)
reg = arr;
while (start2 <= end2)
reg = arr;
for (k = start; k <= end; k++)
arr = reg;
}
void merge_sort(int arr[], const int len) {
int reg;
merge_sort_recursive(arr, reg, 0, len - 1);
}
我不太看得懂此算法的思路，求大佬具体解释。
以及请问其中
while (start1 <= end1 && start2 <= end2)
reg = arr < arr ? arr : arr;
while (start1 <= end1)
reg = arr;
while (start2 <= end2)
reg = arr;
三个while的作用是什么？
以及请问
arr = reg;
的作用是什么？ 这是一种经典的归并排序算法，主要思想是将数组分成两部分，对每一部分递归地进行排序，最后将两个有序的子序列合并成一个有序的序列。这个算法的时间复杂度为O(nlogn)。下面我来详细解释一下代码实现。
merge_sort函数是归并排序的主函数，它调用了merge_sort_recursive函数。merge_sort_recursive函数是递归实现的，它将数组分成两部分，对每一部分递归地进行排序，最后将两个有序的子序列合并成一个有序的序列。
在merge_sort_recursive函数中，首先判断start和end的大小关系，如果start>=end，说明数组只有一个元素或者没有元素，已经有序了，直接返回。否则，计算出中间位置mid，将数组分成两部分和，对这两部分分别进行递归排序。
在递归排序完成之后，将两个有序的子序列合并成一个有序的序列。这个过程中需要借助一个辅助数组reg。首先，将两个子序列的起始位置分别记为start1和start2，将两个子序列的结束位置分别记为end1和end2。然后，比较两个子序列的第一个元素，将较小的元素放入reg数组中，并将对应的指针后移一位，直到其中一个指针超出了对应的结束位置。最后，将剩余的元素依次放入reg数组中。
最后，将reg数组中的元素复制到原数组arr中，完成排序。
至于你提到的三个while循环，第一个while循环是将两个子序列合并到reg数组中，第二个和第三个while循环是将剩余的元素放入reg数组中。
而arr = reg的作用是将排序后的数组从辅助数组reg中复制回原数组arr中，以便于下一次的排序。
希望这个解释能够帮到你。 isdkz 发表于 2023-9-21 14:06
这是一种经典的归并排序算法，主要思想是将数组分成两部分，对每一部分递归地进行排序，最后将两个有序的子 ...
请问
reg = arr < arr ? arr : arr
的运算顺序是怎样的？
页:
[1]