内置排序算法为什么这么快？

2016-4-24 9:8:2
收藏：0
阅读：83
评论：3

快速排序被认为是在列表/表格/任何数据内部排序数据中最快速的算法之一。无论如何，为什么 rosettacode Lua 实现这个算法

function quicksort(t)
    if #t < 2 then return t end
    local pivot = t[1]
    local a, b, c={}, {}, {}
    for _, v in ipairs(t) do
        if v < pivot then a[#a + 1] = v
        elseif v > pivot then c[#c + 1] = v
        else b[#b + 1] = v
        end
    end
    a = quicksort(a)
    c = quicksort(c)
    for _, v in ipairs(b) do a[#a + 1] = v end
    for _, v in ipairs(c) do a[#a + 1] = v end
    return a
end

为什么比内置的table.sort(table)算法慢这么多（需要约一分钟才能对一百万个条目的随机放置表进行排序），后者只需要约五秒钟就能对相同的表进行排序呢？

点赞
用户1009479
用户1009479

Lua 内置的 table.sort 函数同样使用快速排序算法。 (见 其代码)

主要的不同在于内置的函数是使用 C 语言编写的。尽管相对于其他脚本语言来说 Lua 已经很快了，但仍然没有 C 语言那么快。

2016-04-24 09:19:20
用户14000169
用户14000169

你应该将你的枢轴设置为 t[2] ，在我的编译器中可以使性能翻倍，但是根据你如何实现快速排序，它可能会打破它。

2020-07-26 23:47:05
用户312586
用户312586

除了语言上的差异外，Lua 的内置 table.sort 在原地修改目标表的顺序。您的实现返回一个新表，_每个迭代步骤实例化 3 个新表_。我认为这就是大部分性能损失的原因。当对数百万个项的数组进行排序时，这些额外的表分配会迅速增加！

更合适的比较将是进行 _原地快速排序_：

local quicksort do
  local function qhelp(t, l, r)
    if r - l < 1 then return end
    local p = l
    for i = l + 1, r do
      if t[i] < t[p] then
        if i == p + 1 then
          t[p],t[p+1] = t[p+1],t[p]
        else
          t[p],t[p+1],t[i] = t[i],t[p],t[p+1]
        end
        p = p + 1
      end
    end
    qhelp(t, l, p - 1)
    qhelp(t, p + 1, r)
  end

  function quicksort(t)
    qhelp(t, 1, #t)
  end
end

用法：

local arr = { 1, 5, 2, 17, 11, 3, 1, 22, 2, 37 }
quicksort(arr)
print(table.concat(arr,","))

请注意，如果不能修改输入表，则将其复制到牺牲表中并在原地对其进行排序也比“纯”实现更快。

2020-10-11 11:33:17

作者:

用户6245072

用户6245072
推荐文章