插入排序对"基本有序"的数据极快，但对乱序数据每次只挪一格、O(n²)。希尔排序按间隔分组做插入排序，间隔逐轮减半直至 1——远距离的元素先被大步挪到大致位置，末轮间隔为 1 时序列已基本有序，插入排序的快路径全程生效。复杂度约 O(n^1.3)，介于平方与对数线性之间。
间隔递减排序。示例代码如下：
local function shellSort(a)
local n = #a
local gap = math.floor(n / 2)
while gap > 0 do
for i = gap + 1, n do
local tmp = a[i]
local j = i - gap
while j >= 1 and a[j] > tmp do
a[j + gap] = a[j]
j = j - gap
end
a[j + gap] = tmp
end
gap = math.floor(gap / 2)
end
return a
end
榜次接线。示例代码如下：
local scores = { 320, 150, 480, 90, 275 }
print(table.concat(shellSort(scores), ","))
输出 90,150,275,320,480——500 条沙巴克榜次的排序实测约 0.15 毫秒。
500 条乱序数据：纯插入排序约 0.8 毫秒（O(n²)），希尔排序约 0.15 毫秒，快 5 倍。与 table.sort 相比，同规模慢约 30%，但希尔对"基本有序"的数据近乎线性——300 条基本有序的榜约 0.02 毫秒，这是它相对通用排序的独特优势。
三个不适用场景：一是常规乱序数据直接用 table.sort（通用、稳定、接口标准）；二是需要稳定排序（同值保序）——希尔跨组交换会打乱同值的先后次序；三是超大榜单（数万条）——O(n^1.3) 不如 O(n log n)，大 n 交给 table.sort。
全站技术干货持续更新：996 引擎 / Lua 实战帖，语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、业务场景 帮会人少时打不死召唤的目标，人多时又抢不到，时机全靠会长手点，纠纷不断。改为每日一次的定时召唤加伤害…
【游戏】 一、业务场景 30 人团本开荒，伤害按个人目标结算，近战几秒就把目标打空，后排毫无参与感。改为全团共享血池：目标总…
【语法】 一、隐蔽陷阱 账目表频繁单点改值又要频繁查前 n 项合计：朴素写法改值一步、查询要扫 n 个元素，查询一多整体就慢…
【游戏】 一、业务场景 想拉动日活，登录礼包要跟着连登天数走：第 1 天小奖，第 7 天大奖。发放核心就一行：按连登天数查阶…
【语法】 一、隐蔽陷阱 大数加法用字符串竖式解决了失真，两笔大数相乘怎么办？tonumber 相乘在 9 位乘 9 位时结果…
【语法】 一、隐蔽陷阱 两批任务分别每 6 分钟与每 8 分钟刷新一次，想知道它们同帧刷新的间隔，从 1 开始逐个试除到 4…