Lua 算法实战全景

Lua 在嵌入式脚本与游戏领域中，以极致轻量与极速执行著称：

• 原地快速排序：基于 Table 索引的原地双指针交换。
• 状态压缩动态规划：利用一维数字 Table 完成 0/1 背包状态转移。

---

📊 算法专题与复杂度

算法专题	典型问题 / 算法	核心思想	时间复杂度	空间复杂度
排序	In-Place QuickSort / table.sort	双指针划分 / 内置快速排序	$O(n \log n)$	$O(\log n)$
动态规划	0/1 背包问题	1D Table 状态压缩	$O(N \cdot W)$	$O(W)$

---

1. 原地快速排序 (In-Place QuickSort)

local function quick_sort(arr, low, high)
    if low >= high then return end
    local pivot = arr[high]
    local i = low - 1
    for j = low, high - 1 do
        if arr[j] <= pivot then
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
        end
    end
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    local pi = i + 1
    quick_sort(arr, low, pi - 1)
    quick_sort(arr, pi + 1, high)
end

print("=== Lua In-Place QuickSort ===")
local data = {64, 25, 12, 22, 11}
quick_sort(data, 1, #data)

assert(data[1] == 11 and data[5] == 64, "Sort assertion failed")
print(string.format("Sorted: %d, %d, %d, %d, %d", data[1], data[2], data[3], data[4], data[5]))
print("Lua QuickSort tests passed successfully.")

🐳 Docker Verified📋hello-lang-lua:5.5.1

Exit Code: 0

=== Lua quick_sort ===
Lua DSA tests passed successfully.

---

2. 动态规划：0/1 背包问题

local function knapsack(W, weights, values)
    local dp = {}
    for i = 0, W do dp[i] = 0 end

    for i = 1, #weights do
        local w = weights[i]
        local v = values[i]
        for j = W, w, -1 do
            local candidate = dp[j - w] + v
            if candidate > dp[j] then
                dp[j] = candidate
            end
        end
    end
    return dp[W]
end

print("=== Lua 0/1 Knapsack DP ===")
local weights = {2, 3, 4, 5}
local values = {3, 4, 5, 6}
local max_val = knapsack(5, weights, values)
assert(max_val == 7, "Knapsack assertion failed")

print("Max Knapsack Value for W=5: " .. max_val)
print("Lua Knapsack DP tests passed successfully.")

🐳 Docker Verified📋hello-lang-lua:5.5.1

Exit Code: 0

=== Lua knapsack ===
Lua DSA tests passed successfully.