lua 快速排序算法

快速排序是一种高效的排序算法，它的基本思想是通过一次排序将数组分成两个子数组，其中一个子数组的所有元素都比另一个子数组的所有元素小，然后再分别对这两个子数组递归地进行快速排序。

以下是使用Lua语言实现快速排序的示例代码：

function quickSort(arr, left, right)
    left = left or 1
    right = right or #arr
    if left >= right then
        return
    end
    local pivotIndex = partition(arr, left, right)
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
end

function partition(arr, left, right)
    local pivot = arr[right]
    local i = left - 1
    for j = left, right - 1 do
        if arr[j] < pivot then
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
        end
    end
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1
end

-- 测试
local arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
quickSort(arr)
for i, v in ipairs(arr) do
    print(v)
end

在上面的代码中，quickSort函数接收一个数组arr和两个可选参数left和right作为参数，其中left和right分别表示需要排序的子数组的左右边界，如果没有传递这两个参数，默认将整个数组排序。在快速排序中，我们首先通过partition函数将数组分成两个子数组，然后再对这两个子数组递归地进行快速排序。

在partition函数中，我们选择数组中的最后一个元素作为pivot，然后通过一次循环将数组分成两个子数组，其中一个子数组的所有元素都比pivot小，另一个子数组的所有元素都比pivot大。最后，将pivot交换到子数组的中间位置，返回pivot的索引。

在测试代码中，我们使用了一个随机数组进行测试，并打印出排序后的结果。