关于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]