"无长"快速排序算法

Question

我一直在研究排序算法.到目前为止,我发现的所有排序算法要么依赖于已知长度(几乎所有排序算法.我不能使用它们,因为"正确"长度是O(n)),或者比快速排序慢(例如插入分类).

在Lua中,有两个长度概念:

• 适当的序列长度
  • 是O(n)
  • 由ipairs等使用
• 序列长度
  • 是O(log n)
  • 有洞(零值)
  • 由table.insert等使用

我已经研究过heapsort,但是heapsort需要构建一个堆,然后排序.它不能同时作为单个操作,这意味着它仍然存在O(n)长度问题.

使用插入排序,您只需运行插入排序算法,直到您点击第一个nil.这只排序表的"正确序列"部分(即,从1到n的键没有任何nil值),但插入排序比quicksort慢.

是否有任何就地排序算法,如插入排序,不依赖于长度,但性能可与快速排序相媲美？

示例插入排序代码(在维基百科的帮助下):

function isort(t)
  -- In-place insertion sort that never uses the length operator.
  -- Stops at the first nil, as expected. Breaks if you use "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}

Answer 1

由于排序本身必须至少占用O(n log n),因此额外的O(n)扫描似乎不会使算法无效.使用二次算法(如插入或冒泡排序)是错误的经济.

您可以使用heapsort变体,只需迭代地插入到不断增长的堆中,而不是使用O(n)buildheap算法.即使你逐步构建堆,Heapsort肯定是O(n log n),但我怀疑它是否与quicksort竞争.(它对于大输入的插入排序肯定具有竞争力,特别是相反的大输入.)

您可以在维基百科中看到标准堆的伪代码.我的下面的伪代码的不同之处在于它不需要将数组的大小作为参数,而是将其作为结果返回.它还使用基于1的载体,而不是从0开始的,因为你正在使用的Lua,所以a是假设从运行a[1]到a[count]了一些价值count.

 procedure heapsort(a):
     input: an array of comparable elements
     output: the number of elements in the array.

     (Heapify successive prefixes of the array)
     count ? 1
     while a has an element indexed by count:
         siftup(a, count)
         count ? count + 1
     count ? count - 1

     (Extract the sorted list from the heap)
     i ? count
     while i > 1:
         swap(a, 1, i)
         i ? i - 1
         siftdown(a, i)

     return count

siftup并且siftdown是标准堆函数,这里以1为基础的版本提供.提供的代码使用标准优化,其中筛选通过单次旋转而不是一系列交换完成; 这显着减少了数组引用的数量.(该swap在heapsort程序可以被集成到siftdown了一个轻微的额外储蓄,但它掩盖了算法,如果你想用这种优化,改变val ? a[1]到val ? a[count + 1]; a[count + 1] ? a[1]并删除swap从heapsort).

在基于1堆,节点的父i是节点floor(i/2)和节点的孩子i是节点2i和2i+1.回想一下,堆约束要求每个节点都不小于其父节点.(这会产生一个minheap,用于产生降序排序.如果你想要一个升序排序,你需要一个maxheap,这意味着将下面的三个值比较>改为<.)

procedure siftup(a, count):
    input: a vector of length count, of which the first count - 1
           elements satisfy the heap constraint.
    result: the first count elements of a satisfy the heap constraint.

    val ? a[count]
    loop:
        parent ? floor(count / 2)
        if parent == 0 or val > a[parent]:
            a[count] ? val
            return
        else
            a[count] ? a[parent]
            count ? parent

procedure siftdown(a, count):
    input: a vector of length count which satisfies the heap constraint
           except for the first element.
    result: the first count elements of a satisfy the heap constraint.

    val ? a[1]
    parent ? 1
    loop :
        child ? 2 * parent
        if child < count and a[child] > a[child + 1]:
            child ? child + 1
        if count < child or not (val > a[child]):
            a[parent] ? val
            return
        else
            a[parent] ? a[child]
            parent ? child