Lua 排序算法

归并排序（Merge Sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并操作(Merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序, 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

算法步骤

1. 把 n 个记录看成 n 个长度为 1 的有序子表
2. 进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
3. 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。

动画演示

Lua 实现

local function mergeSort(arr, low, high)
    local low = low
    local high = high
    if high - low < 1 then return end
<span class="kd">local</span> <span class="n">mid</span> <span class="o">=</span> <span class="nb">math.floor</span><span class="p">((</span><span class="n">low</span><span class="o">+</span><span class="n">high</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">)</span>
<span class="c1">-- 递归的拆分子序列</span>
<span class="n">mergeSort</span><span class="p">(</span><span class="n">arr</span><span class="p">,</span> <span class="n">low</span><span class="p">,</span> <span class="n">mid</span><span class="p">)</span>
<span class="n">mergeSort</span><span class="p">(</span><span class="n">arr</span><span class="p">,</span> <span class="n">mid</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">high</span><span class="p">)</span>

<span class="c1">-- i, m 代表一个序列中的低高位</span>
<span class="c1">-- m+1，high 代表相邻的另外一个序列（right序列）的低高位</span>
<span class="kd">local</span> <span class="n">i</span><span class="p">,</span> <span class="n">m</span> <span class="o">=</span> <span class="n">low</span><span class="p">,</span> <span class="n">mid</span>
<span class="kd">local</span> <span class="n">temp</span>
<span class="k">while</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span> <span class="ow">and</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">high</span> <span class="k">do</span>
    <span class="k">if</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">arr</span><span class="p">[</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="k">then</span>
        <span class="n">temp</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span>
        <span class="c1">-- 迭代left序列</span>
        <span class="c1">-- 之所以这么迭代是因为我们本质上还是在arr中</span>
        <span class="k">for</span> <span class="n">j</span> <span class="o">=</span> <span class="n">m</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span> <span class="k">do</span>
            <span class="n">arr</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="n">j</span><span class="p">]</span>
        <span class="k">end</span>
        <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">temp</span>
        <span class="n">m</span> <span class="o">=</span> <span class="n">m</span> <span class="o">+</span> <span class="mi">1</span>
    <span class="k">else</span>
        <span class="n">i</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span>
    <span class="k">end</span>
<span class="k">end</span>

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

}

mergeSort(list, 1, #list)

print(table.concat(list, ", "))

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