您可以在维基百科上阅读此内容:
function merge_sort(list m)
// Base case. A list of zero or one elements is sorted, by definition.
if length(m) <= 1
return m
// Recursive case. First, *divide* the list into equal-sized sublists.
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
add x to left
for each x in m after or equal middle
add x to right
// Recursively sort both sublists
left = merge_sort(left)
right = merge_sort(right)
// Then merge the now-sorted sublists.
return merge(left, right)
第 1 行有一个数字列表,比方说 9 6 3 7 5 1 8 2
他们说 merge_sort 在 2 和 2 上一次又一次地划分列表,直到每个列表只剩下 1 个整数,就像这个:
9 6 3 7 5 1 8 2 -->
9 6 3 7 - 5 1 8 2 -->
9 6 - 3 7 - 5 1 - 8 2 -->
9 - 6 - 3 - 7 - 5 - 1 - 8 - 2
然后数字像这样放在一起:
6 9 - 3 7 - 1 5 - 2 8 -->
3 6 7 9 - 1 2 5 8 -->
1 2 3 5 6 7 8 9 -->
但我没看到代码中的整数列表在哪里一次又一次地除以 2,直到每个只剩下 1 个整数?
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
add x to left
for each x in m after or equal middle
add x to right
据我了解,在上面的代码中,数字列表分为两个不同的列表: 9 6 3 7 和 5 1 8 2
下面的代码会发生什么?
left = merge_sort(left)
right = merge_sort(right)
谁能给我解释一下上面的 merge_sort 代码是如何一步步工作的?
最佳答案
But I don't see where in the code the list of integers are divided on 2 again and again until each has only 1 integer left?
var list left, right
var integer middle = length(m) / 2 --------statement-1
for each x in m before middle --------statement-2
add x to left
for each x in m after or equal middle --------statement-3
add x to right
在 statement-1
中,您将数组分成两部分并将它们添加到 left
和 right
子数组中。在 statement-2
中,您添加了 middle
之前的所有元素,这是数组的中间元素。类似地,statement-3
,您要在右子数组中添加其余元素。所以本质上,您继续将数组分成两部分,直到它们的大小为 1
或 0
。
if length(m) <= 1
return m
一开始你有上面的条件检查,如果数组的大小小于或等于一,它返回方法调用。
What then happens on the code below?
left = merge_sort(left)
right = merge_sort(right)
这是对每个子数组进行排序(划分数组直到大小为一)的递归调用。这是在上面的伪代码中创建的。您分别对 left
和 right
子数组进行排序,然后将它们连接到一个数组中。
return merge(left, right)
此处 left
和 right
子数组都传递给 merge
函数。这两个数组都是排序数组。 merge
函数的任务是将这些子数组合并为一个排序数组。
关于algorithm - 我知道合并排序是如何工作的,但合并排序代码是如何工作的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32506758/