Lua合并排序错误

Question

我试图通过编写一个基本的合并排序来学习Lua，但是由于我也不熟悉合并排序，所以我遇到了一些问题。

代码:

arr = {}
status = 0


function return_first_half (list)
    size = #list
    size = size / 2
    t = {}
    for var = 1, size, 2 do
        t[var] = list[var]
    end
    return t
end

function return_last_half (list)
    size = #list
    i = size / 2
    t = {}
    for var = size, i, -1 do
        t[var] = list[var]
    end
    return t
end


function msort (list)
    size = #list
    first_half = {}
    last_half  = {}
    if (size <= 1) then
        return list
    end
    first_half = msort(return_first_half(list))
    last_half = msort(return_last_half(list))
    if (#first_half == 1) then
        if (#last_half == 1) then
            if (first_half[1] > last_half[1]) then
                arr[status] = first_half[1]
                status = status + 1
                arr[status] = last_half[1]
                status = status + 1
            end
            if (first_half[1] < last_half[1])then
                arr[status] = last_half[1]
                status = status + 1
                arr[status] = first_half[1]
                status = status + 1
            end
        end
    end
end

function main ()
    list = {}
    for i = 1, 8, 1 do
        list[i] = io.read()
    end
    msort(list)
    for i = 1, #arr, 1 do
        print (arr[i])
    end
end

main()

当我输入 8 递减到 1 时，它会打印 nil 并退出。有什么帮助吗？

编辑:修复了数组长度和地址的问题，它现在在以下行返回堆栈溢出:

first_half = msort(return_first_half(list))

Answer 1

问题是，由于计算/复制前半部分和后半部分的错误，你永远不会退出递归。

但在开始之前，让我指出您应该始终使用局部变量在函数内部进行临时存储。它速度更快，并且不会使全局表变得困惑。实际上你应该总是使用local(拜托，请习惯id)除非你真的觉得你需要设置一个全局变量。

现在回到主题: 在 return_first_half 中，您复制每隔一个项目。这是为什么？如果您想允许不均匀的表格大小，您还应该使用 math.floor(size/2)。

在return_second_half中也是如此。我会将其更改为:

function return_last_half (list)
    size = #list
    i = math.floor(size / 2) + 1
    t = {}
    local itemno = 1
    for var = i, size do
        t[itemno] = list[var]
    end
    return t
end

您的版本存在问题:

• 当表格大小不均匀时，您会得到小数
• 您正在返回表中的相同位置设置项目，即 5、6、7、8。这意味着大小 # 运算符返回 8，尽管项目数量为 4 .实际上，每当数组中有间隙时，大小运算符的行为都是未定义的。

总的来说，你的算法设计得不是很好，所以我不会再深入。我已经告诉您如何避免堆栈溢出，因此如果您愿意，可以从那里获取它。

但是让我给你介绍一下我的归并排序的快速实现，它对项目进行排序(将它们放回到同一个表中):

local function merge(list, start, middle, stop)
    local temp = {}
    local itemno = 1
    local item1, item2 = start, middle + 1

    while item1 <= middle and item2 <= stop do
        if list[item2] < list[item1] then
            temp[itemno] = list[item2]
            item2 = item2 + 1
        else
            temp[itemno] = list[item1]
            item1 = item1 + 1
        end
        itemno = itemno + 1
    end

    if item1 <= middle then
        while item1 <= middle do
            temp[itemno] = list[item1]
            itemno = itemno + 1
            item1 = item1 + 1
        end
    else
        while item2 <= stop do
            temp[itemno] = list[item2]
            itemno = itemno + 1
            item2 = item2 + 1
        end
    end

    itemno = 1
    for i = start, stop do
        list[i] = temp[itemno]
        itemno = itemno + 1
    end
end

local function msort(list, start, stop)
    if stop - start == 0 then
        return list
    elseif start > stop then
        error("Oh crap")
    end

    local middle = math.floor((stop + start) / 2)
    msort(list, start, middle)
    msort(list, middle + 1, stop)
    merge(list, start, middle, stop)
end

local function main ()
    list = {}
    print("Enter number of items:")
    local i = tonumber(io.read())
    for item = 1, i do
        print("Enter item number " .. item .. ":")
        list[item] = tonumber(io.read())
    end
    msort(list, 1, i)
    for k, v in ipairs(list) do
        print (v)
    end
end

main()

编辑:

关于这个简单的递归实现，需要注意的一件事是，如果列表足够大，无论如何你都会遇到堆栈溢出。