"Lengthless"快速排序算法

我一直在研究排序算法。到目前为止，我发现所有的排序算法都要么依赖一个已知的长度(几乎所有的排序算法都不能用，因为"正确"的长度是O(n)),要么比快速排序还慢(例如插入排序)。

在Lua中，有两个长度的概念:

• 合适的序列长度

  • 是O(n)
  • 由ipairs等使用

• 序列长度

  • 是O(log n)
  • 有洞(无值)

  -由table.insert等使用

我研究了堆排序，但堆排序需要构建一个堆，然后排序。它不能作为单个操作完成两者，这意味着它仍然会遇到O(n)长度问题。

插入排序只需运行插入排序算法，直到第一个'nil'为止。这仅对表格的“适当序列”部分进行排序(即，从1到n的键，没有任何nil值)，但插入排序比快速排序慢。

有没有类似于插入排序的就地排序算法，不依赖于长度，但具有与快速排序相当的性能？

示例插入排序代码(有一些来自维基百科的帮助):

function isort(t)
  --不使用长度运算符的就地插入排序。停止于第一个nil，如预期。如果使用“for i = 1, #t do ”，则会中断
  for i in ipairs(t) do
      local j = i
      while j > 1 and t[j-1] > t[j] do
          t[j], t[j-1] = t[j-1], t[j]
          j = j - 1
      end
  end
end

local t = {6, 5, 3, 1, 7, 2, 4, nil, 1, 1, 8, 3, 4, nil, nil, 1}
isort(t)
io.write("{")
if #t > 0 then
  io.write(tostring(t[1]))
  for i=2, #t do
    io.write(", ")
    io.write(tostring(t[i]))
  end
end
io.write("}\n")
-- stdout:
-- {1, 2, 3, 4, 5, 6, 7, nil, 1, 1, 8, 3, 4, nil, nil, 1}