快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

算法步骤
  1. 从数列中挑出一个元素,称为 “基准”(pivot)
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作
  3. 对 “基准” 左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
动画演示

Alt text

Lua 实现
local function partition(list, low, high)
    local low = low
    local high = high
    local pivotKey = list[low] -- 定义一个中介值
<span class="c1">-- 下面将中介值移动到列表的“中间”</span>
<span class="c1">-- 当左索引与右索引相邻时停止循环</span>
<span class="k">while</span> <span class="n">low</span> <span class="o">&lt;</span> <span class="n">high</span> <span class="k">do</span>
    <span class="c1">-- 假如当前右值大于等于中介值则右索引左移</span>
    <span class="c1">-- 否则交换中介值和右值位置</span>
    <span class="k">while</span> <span class="n">low</span> <span class="o">&lt;</span> <span class="n">high</span> <span class="ow">and</span> <span class="n">list</span><span class="p">[</span><span class="n">high</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">pivotKey</span> <span class="k">do</span>
        <span class="n">high</span> <span class="o">=</span> <span class="n">high</span> <span class="o">-</span> <span class="mi">1</span>
    <span class="k">end</span>
    <span class="n">list</span><span class="p">[</span><span class="n">low</span><span class="p">],</span> <span class="n">list</span><span class="p">[</span><span class="n">high</span><span class="p">]</span> <span class="o">=</span> <span class="n">list</span><span class="p">[</span><span class="n">high</span><span class="p">],</span> <span class="n">list</span><span class="p">[</span><span class="n">low</span><span class="p">]</span>

    <span class="c1">-- 假如当前左值小于等于中介值则左索引右移</span>
    <span class="c1">-- 否则交换中介值和左值位置</span>
    <span class="k">while</span> <span class="n">low</span> <span class="o">&lt;</span> <span class="n">high</span> <span class="ow">and</span> <span class="n">list</span><span class="p">[</span><span class="n">low</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">pivotKey</span> <span class="k">do</span>
        <span class="n">low</span> <span class="o">=</span> <span class="n">low</span> <span class="o">+</span> <span class="mi">1</span>
    <span class="k">end</span>
    <span class="n">list</span><span class="p">[</span><span class="n">low</span><span class="p">],</span> <span class="n">list</span><span class="p">[</span><span class="n">high</span><span class="p">]</span> <span class="o">=</span> <span class="n">list</span><span class="p">[</span><span class="n">high</span><span class="p">],</span> <span class="n">list</span><span class="p">[</span><span class="n">low</span><span class="p">]</span>
<span class="k">end</span>
<span class="k">return</span> <span class="n">low</span>

end

local function quickSort(list, low, high)
if low < high then
– 返回列表中中介值所在的位置,该位置左边的值都小于等于中介值,右边的值都大于等于中介值
local pivotKeyIndex = partition(list, low, high)
– 分别将中介值左右两边的列表递归快排
quickSort(list, low, pivotKeyIndex - 1)
quickSort(list, pivotKeyIndex + 1, high)
end
end

local list = {
-81, -93, -36.85, -53, -31, 79, 45.94, 36, 94, -95.03, 11, 56, 23, -39,
14, 1, -20.1, -21, 91, 31, 91, -23, 36.5, 44, 82, -30, 51, 96, 64, -41
}
quickSort(list, 1, #list)
print(table.concat(list, ", "))

值得注意的是 Lua 自带的table.sort就是使用的快排,性能肯定比这个纯 Lua 的版本要好

            <hr style="visibility: hidden;"/>