保存内存的合并排序

首先,怎么做?你…吗 继续覆盖临时数组 合并?

是的,临时数组一直被覆盖。在合并阶段使用临时数组保存合并结果,然后在合并结束时将其复制回永久数组。

第二个让人困惑,因为我 为什么它必须是 与合并排序不同的方法。

merge_sort_1 merge_sort 只是一个方便的函数,创建临时数组并填充初始的开始和结束位置。

我也不知道为什么 已通过开始和结束索引。在 事实上,也许我读错了什么,但是 指令听起来像 合并排序1不做任何实际工作。

因为我看不到 拆分位置的说明 做两个原来的一半 合并排序?

递归函数 合并排序1

我可以用Lua编写合并排序,并且可以对我的实现进行评论。这些指示似乎是通过书面形式写出来的,就好像是对教师执行情况的评论。

这是 合并排序 功能。正如我所说,这只是一个方便的功能,我觉得不是肉的问题。

-- Write a top level procedure merge_sort that takes as its argument
-- the array to sort.
function merge_sort(a)
    -- It should declare a temporary array and then call merge_sort_1,
    -- a procedure of four arguments: The array to sort, the one to use
    -- as temporary space, and the start and finish indexes within which
    -- this call to merge_sort_1 should work.
    merge_sort_1(a,{},1,#a)
end

看看 this 解释,用花哨的动画来帮助你理解它。

这是他们的伪代码版本:

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

看看他们如何使用b来保存数据的临时副本? 你的老师想要的是你把一张桌子交进去,用来临时存放。

这能解决任务吗?

您的主要排序例程如下:(对不起,我不知道Lua,所以我将编写一些Javaish代码)

void merge_sort(int[] array) {
  int[] t = ...allocate a temporary array...
  merge_sort_1(array, 0, array.length, t);
}

merge_sort_1 获取要排序的数组、一些开始和完成索引以及用于某些临时空间的数组。它执行实际的分而治之的调用,并调用 merge 例行公事。注意,递归调用需要转到 合并排序1 而不是 merge_sort

我会让你写一个 合并