Lua排序算法实现异常求助：含重复大数时失效

嘿，我之前在Lua里实现排序算法的时候也踩过类似的坑！虽然没看到你的具体代码，但处理包含大量重复元素的数据集时翻车，大概率是这几个常见问题导致的，你可以对照自己的代码排查：

• 基准值选择的问题：如果你的算法是快速排序这类依赖基准值的实现，要是每次都选数组的首尾元素当基准，遇到大量重复元素时会直接导致分区极度不平衡，时间复杂度瞬间飙升到O(n²)，甚至可能因为递归深度太大触发栈溢出，看起来就像“无法正常运行”。很多入门版的快排都没考虑这种极端情况，把所有等于基准的元素全分到同一侧，直接拖垮了排序效率。

• 重复元素的分区逻辑缺失：不少排序实现里只处理了“小于基准”和“大于基准”的元素，完全忽略了“等于基准”的情况。这些重复元素会被反复卷入排序过程，不仅浪费性能，还可能导致最终结果里重复元素的位置混乱，甚至出现未排序的片段。

• 边界条件处理错误：比如在遍历或递归调用时，没正确跳过已经处理过的重复元素，或者边界索引设置错误（比如把包含基准值的索引再次传入递归），导致部分元素被重复排序或者根本没被处理。

给你一个优化过的Lua快速排序实现，专门处理了重复元素的情况，用三路分区的思路：

function quickSort(arr, low, high)
    -- 初始化边界，默认处理整个数组
    low = low or 1
    high = high or #arr
    -- 递归终止条件：分区只有一个元素或为空
    if low >= high then return end

    -- 优化基准值选择：取中间元素，避免极端有序/重复场景下的分区失衡
    local mid = math.floor((low + high) / 2)
    arr[mid], arr[high] = arr[high], arr[mid]
    local pivot = arr[high]

    -- 三路分区：小于pivot的元素在[low, i]，等于pivot的在[i+1, eq]，大于的在[eq+1, high]
    local i = low - 1
    local eq = low - 1

    for j = low, high do
        if arr[j] <= pivot then
            eq = eq + 1
            arr[i+1], arr[eq] = arr[eq], arr[i+1]
            if arr[eq] < pivot then
                i = i + 1
            end
        end
    end

    -- 只递归处理小于和大于pivot的分区，等于的部分已经有序，无需再处理
    quickSort(arr, low, i)
    quickSort(arr, eq + 1, high)
end

-- 测试包含大量重复元素的数组
local testArr = {3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,5,8,8,7,9,9,3,2,3,8,4,6,2,6,4}
quickSort(testArr)
-- 打印排序结果
for _, val in ipairs(testArr) do
    io.write(val .. " ")
end

这个实现的核心是把数组分成了三个部分，等于基准值的元素直接跳过递归处理，既提升了效率，又避免了重复元素导致的各种问题。

如果你的算法不是快速排序，比如是冒泡或插入排序，那可能是重复元素导致的交换逻辑错误——比如冒泡排序里没处理相等元素的情况，导致不必要的交换甚至顺序错乱，但这类算法一般不会在大数据集上完全失效，更多是效率极低。

内容的提问来源于stack exchange，提问作者PloxyThing