algorithm - Lua 创建的快速排序无法正常工作

Question

我是最近在研究Lua的人。我正在用 Lua 编写 QuickSort。我把自己用Go语言写的快速排序代码翻译成了Lua，代码如下。 Table.slice 函数定义了在 QuickSort 中进行递归调用时使用的函数。

function table.slice(tbl, first, last, step)
    local sliced = {}

    for i = first , last , step  do
        sliced[#sliced+1] = tbl[i]
    end

    return sliced
end

function quickSort(array)
    if #array < 2 then 
        return array
    end

    local left = 1
    local right =  #array
    local pivot = math.random( 1, #array )

    array[pivot], array[right] = array[right], array[pivot]

    for i = 1, #array do
        if array[i] > array[right] then
            array[left], array[i] = array[i], array[left]

            left = left + 1
        end
    end

    array[left], array[right] = array[right], array[left]

    a = table.slice(array,1,left-1,1)
    b = table.slice(array,left+1,#array,1)
    quickSort(a)
    quickSort(b)

    return array
end

我一开始以为我搞错了Lua的表索引是从1开始的，但是我也说不出哪里错了。你能告诉我哪里错了吗？谢谢。

Answer 1

我修改了代码，直接修改给定的表，将范围值作为参数与注释一起传递，然后发布快速排序代码。

function quickSort(array, le, ri)
    if ri-le < 1 then 
        return array
    end

    local left = le
    local right =  ri
    local pivot = math.random( le, ri )

    array[pivot], array[right] = array[right], array[pivot]

    for i = le, ri do
        if array[i] > array[right] then
            array[left], array[i] = array[i], array[left]

            left = left + 1
        end
    end

    array[left], array[right] = array[right], array[left]

    quickSort(array, 1, left-1)
    quickSort(array, left +1, ri)

    return array
end