马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
已知以下代码: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的作用是什么?
以及请问的作用是什么?
这是一种经典的归并排序算法,主要思想是将数组分成两部分,对每一部分递归地进行排序,最后将两个有序的子序列合并成一个有序的序列。这个算法的时间复杂度为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中,以便于下一次的排序。
希望这个解释能够帮到你。
|