lua - 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

The problem is that you never get out of the recursion due to an error in calculating / copying the first and the second half.

But before I start, let me point out that you should always use local variables for temporary storage inside functions. It's much faster and doesn't clutter the global table. Actually you should always use local (please, please get used to id) unless you really feel you need to set a global variable.

Now back to the topic: In return_first_half you copy every second item. Why is that? You should also use math.floor(size/2), if you want to allow uneven table sizes.

Similarily in return_second_half. I would change it to:

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

Problems in your version:

• you get fractional numbers when table size is uneven
• you're setting items in the same positions in the return table, that is 5, 6, 7, 8. That means that the size # operator returns 8, although number of items is 4. Actually, whenever you have gaps in the array, the behaviour of size operator is undefined.

In general your algorithm is not very well designed, so I'm not going to go any deeper. I've told you how to avoid stack overflow, so you can take it from there, if you like.

But let me give you my quick implementation of mergesort, which sorts items in place (puts them back in the same table):

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()

EDIT:

One thing to note about this simple, recursive implementation is that you're gonna end up with stack overflow anyway, if the list is large enough.