lua 二分插入排序

Lua是一种轻量级的脚本语言，广泛用于嵌入式系统和游戏开发中。二分插入排序是一种高效的排序算法，它通过将待排序元素插入已排序序列的正确位置来实现排序。下面是Lua中实现二分插入排序的示例代码：

function binaryInsertionSort(arr)
    for i = 2, #arr do
        local key = arr[i]
        local low, high = 1, i - 1

        while low <= high do
            local mid = math.floor((low + high) / 2)
            if arr[mid] > key then
                high = mid - 1
            else
                low = mid + 1
            end
        end

        for j = i - 1, low, -1 do
            arr[j + 1] = arr[j]
        end

        arr[low] = key
    end
end

-- 示例使用
local arr = {5, 2, 8, 9, 1}
binaryInsertionSort(arr)

for i = 1, #arr do
    print(arr[i])
end

以上代码实现了一个名为`binaryInsertionSort`的函数，它接受一个数组作为参数，并对数组进行二分插入排序。在排序过程中，通过不断比较和移动元素，将待排序元素插入到已排序序列的正确位置。