使用lua实现各种算法，先从归并排序算法开始

萧山财神

接下来我们可以实现一种经典的排序算法：归并排序（Merge Sort）。归并排序是一种基于分治法的排序算法，具有稳定性和较好的时间复杂度，广泛应用于需要稳定排序的场景。

归并排序算法简介

归并排序的基本步骤如下：

1. 将数组分成两部分。
2. 递归地对这两部分进行排序。
3. 合并这两部分，使其成为一个有序的数组。

示例代码

以下是用 Lua 实现的归并排序算法：

-- 合并两个有序数组
function merge(arr, left, mid, right)
    local n1 = mid - left + 1
    local n2 = right - mid

    -- 创建临时数组
    local L = {}
    local R = {}

    for i = 1, n1 do
        L[i] = arr[left + i - 1]
    end
    for j = 1, n2 do
        R[j] = arr[mid + j]
    end

    -- 合并临时数组到原数组
    local i = 1
    local j = 1
    local k = left

    while i <= n1 and j <= n2 do
        if L[i] <= R[j] then
            arr[k] = L[i]
            i = i + 1
        else
            arr[k] = R[j]
            j = j + 1
        end
        k = k + 1
    end

    -- 复制剩余元素
    while i <= n1 do
        arr[k] = L[i]
        i = i + 1
        k = k + 1
    end

    while j <= n2 do
        arr[k] = R[j]
        j = j + 1
        k = k + 1
    end
end

-- 归并排序函数
function mergeSort(arr, left, right)
    if left < right then
        local mid = math.floor((left + right) / 2)

        -- 递归排序左半部分
        mergeSort(arr, left, mid)

        -- 递归排序右半部分
        mergeSort(arr, mid + 1, right)

        -- 合并两部分
        merge(arr, left, mid, right)
    end
end

-- 测试归并排序算法
local arr = {12, 11, 13, 5, 6, 7}
local n = #arr

print("排序前的数组:")
for i = 1, n do
    io.write(arr[i] .. " ")
end
print()

mergeSort(arr, 1, n)

print("排序后的数组:")
for i = 1, n do
    io.write(arr[i] .. " ")
end
print()

在这个实现中：

1. merge 函数用于合并两个有序数组。它接受数组 arr、左边界 left、中间位置 mid 和右边界 right 作为输入，将 arr[left..mid] 和 arr[mid+1..right] 合并成一个有序数组。
2. mergeSort 函数是归并排序的主函数，接受数组 arr、左边界 left 和右边界 right 作为输入。它递归地将数组分成两部分，并对这两部分进行排序，然后合并这两部分。
3. 测试代码定义了一个数组，并调用 mergeSort 函数对数组进行排序，输出排序前后的数组。

归并排序在2D游戏中的排序、路径规划、碰撞检测等方面有广泛应用。它能够高效地对数据进行排序，适用于各种需要稳定排序的场景。