尧图网站建设 
-- -- 内省排序Introsort实现模块-- 功能提供复刻标准库 table.sort 语义的内省排序接口-- 供麻将、畅玩阁、小游戏统一调用保证排序效率与最坏复杂度。-- 使用local module_smallgame Include(modules/smallgame)-- module_smallgame.Smallgame_IntroSort(tArr, fnCompare)-- -- 算法结构-- 1. 快速排序三点取中选枢轴 单次划分递归排序正常路径-- 2. 递归深度超限2 * floor(log2(n))时切换为堆排序兜底-- 保证最坏时间复杂度 O(n log n)-- 3. 区间长度不超过 16 时改用插入排序收尾小数组常数极小。-- 语义对齐标准库 table.sort-- - tArr 必须为连续整数键数组1..#tArr原地排序-- - fnCompare(a, b) 返回布尔表示 a 应排在 b 之前缺省用 比较-- - 空表与单元素表直接返回不做任何处理。-- -- 局部化系统库函数热更新不影响提高性能localtypetype-- 获取类型localpairspairs-- 遍历键值对localmath_floormath.floor-- 向下取整localmath_minmath.min-- 取最小值localmath_maxmath.max-- 取最大值localtable_inserttable.insert-- 向表中插入元素localtable_removetable.remove-- 删除表中指定位置的元素-- 插入排序阈值区间长度不超过该值时使用插入排序localINTROSORT_INSERTION_THRESHOLD16-- 深度系数递归深度限制 2 * floor(log2(n))与标准内省排序一致localINTROSORT_DEPTH_FACTOR2-- 深度下限长度不满 2 的区间直接使用插入排序无需进行对数计算localINTROSORT_MIN_DEPTH0-- ----------------------------------------------------------------------------- 插入排序对数组 tArr 的 [nLeft, nRight] 区间做插入排序-- 说明小数组上常数因子小优于快速排序顺带作为内省排序的收尾器。-- 参数tArr 数组nLeft 左边界nRight 右边界含fnCompare 比较器-- ---------------------------------------------------------------------------localfunctioninsertion_sort(tArr,nLeft,nRight,fnCompare)fornIndexnLeft1,nRightdolocaltValuetArr[nIndex]-- 取出待插入元素localnPosnIndex-1-- 从当前元素前一个位置向前扫描whilenPosnLeftandfnCompare(tValue,tArr[nPos])dotArr[nPos1]tArr[nPos]-- 比待插入元素大的整体右移一格nPosnPos-1endtArr[nPos1]tValue-- 待插入元素落入正确位置endend-- ----------------------------------------------------------------------------- 三点取中返回 tArr[nLeft]、tArr[nMid]、tArr[nRight] 三者中位数的下标-- 目的避免取到区间最小/最大元素而退化成倾斜分区-- 对已有序/逆序输入第一趟即可切到中位。-- 参数fnCompare 比较器返回 true 表示前一个参数应排在后面参数之前-- ---------------------------------------------------------------------------localfunctionmedian_of_three(tArr,nLeft,nMid,nRight,fnCompare)-- 处理 nLeft 与 nMid 的比较结果iffnCompare(tArr[nMid],tArr[nLeft])then-- nMid nLeftiffnCompare(tArr[nRight],tArr[nLeft])then-- nMid nRight nLeft中位数为 nRightiffnCompare(tArr[nMid],tArr[nRight])thenreturnnRightelsereturnnMidendelse-- nMid nLeft nRight中位数为 nLeftreturnnLeftendelse-- nLeft nMidiffnCompare(tArr[nRight],tArr[nMid])then-- nRight nMidiffnCompare(tArr[nRight],tArr[nLeft])then-- nRight nLeft nMid中位数为 nLeftreturnnLeftelsereturnnRightendelse-- nLeft nMid nRight中位数为 nMidreturnnMidendendend-- ----------------------------------------------------------------------------- 快速排序单次划分Lomuto 模式-- 说明以枢轴为分界左侧元素全部 枢轴右侧元素全部 枢轴-- 返回枢轴最终落位下标。枢轴值先取出存放到局部变量-- 避免元素交换时枢轴被改写防止比较基准漂移。-- 参数tArr 数组nLeft 左边界nRight 右边界含fnCompare 比较器-- 返回枢轴最终下标 nPivot-- ---------------------------------------------------------------------------localfunctionpartition(tArr,nLeft,nRight,fnCompare)localnMidnLeftmath_floor((nRight-nLeft)/2)-- 中点下标localnPivotIndexmedian_of_three(tArr,nLeft,nMid,nRight,fnCompare)localtPivottArr[nPivotIndex]-- 取出枢轴值-- 将枢轴临时移到区间末尾便于单向扫描tArr[nPivotIndex]tArr[nRight]tArr[nRight]tPivotlocalnStorenLeft-- 小元素放置区边界fornIndexnLeft,nRight-1doiffnCompare(tArr[nIndex],tPivot)then-- 小于枢轴归左区localtTemptArr[nIndex]tArr[nIndex]tArr[nStore]tArr[nStore]tTemp nStorenStore1endend-- 枢轴放回分界处tArr[nRight]tArr[nStore]tArr[nStore]tPivotreturnnStoreend-- ----------------------------------------------------------------------------- 堆排序对数组 tArr 的 [nLeft, nRight] 区间做堆排序递归深度超限兜底-- 说明原地建最大堆 逐次取出堆顶放末尾最坏 O(n log n)、O(1) 额外空间。-- 参数tArr 数组nLeft 左边界nRight 右边界含fnCompare 比较器-- ---------------------------------------------------------------------------localfunctionsift_down(tArr,nLeft,nRange,nRoot,fnCompare)localnLargestnRootlocalnLeftChildnLeft(nRoot-nLeft)*21-- 左子下标localnRightChildnLeftChild1-- 右子下标ifnLeftChildnRangeandfnCompare(tArr[nLargest],tArr[nLeftChild])thennLargestnLeftChildendifnRightChildnRangeandfnCompare(tArr[nLargest],tArr[nRightChild])thennLargestnRightChildendifnLargest~nRootthenlocaltTemptArr[nLargest]tArr[nLargest]tArr[nRoot]tArr[nRoot]tTempsift_down(tArr,nLeft,nRange,nLargest,fnCompare)endendlocalfunctionheap_sort(tArr,nLeft,nRight,fnCompare)localnRangenRight-- 当前堆的右边界-- 建堆从最后一个非叶子结点开始自底向上调整fornIndexmath_floor((nRange-nLeft)/2),0,-1dosift_down(tArr,nLeft,nRange,nLeftnIndex,fnCompare)end-- 依次取出堆顶最大元素放到末尾然后重新调整剩余部分fornIndexnRange,nLeft1,-1dolocaltTemptArr[nLeft]tArr[nLeft]tArr[nIndex]tArr[nIndex]tTempsift_down(tArr,nLeft,nIndex-1,nLeft,fnCompare)endend-- ----------------------------------------------------------------------------- 内省排序主流程递归版-- 说明深度超限时切堆排序兜底深度未超限且区间大于阈值时快排划分-- 区间收窄到阈值内时切插入排序收尾。-- 参数tArr 数组nLeft 左边界nRight 右边界含-- nDepth 剩余递归深度fnCompare 比较器-- ---------------------------------------------------------------------------localfunctionintrosort_impl(tArr,nLeft,nRight,nDepth,fnCompare)whilenRight-nLeft1INTROSORT_INSERTION_THRESHOLDdoifnDepthINTROSORT_MIN_DEPTHthen-- 递归深度超限判定输入病态整段堆排序兜底并结束heap_sort(tArr,nLeft,nRight,fnCompare)returnendnDepthnDepth-1localnPivotpartition(tArr,nLeft,nRight,fnCompare)-- 递归处理右半区不含枢轴左半区交给外层循环继续迭代introsort_impl(tArr,nPivot1,nRight,nDepth,fnCompare)nRightnPivot-1end-- 区间长度收窄到阈值内插入排序收尾insertion_sort(tArr,nLeft,nRight,fnCompare)end-- ----------------------------------------------------------------------------- 默认比较器升序等价于标准库 table.sort 缺省 比较-- 参数a 任意可比值b 任意可比值-- 返回a b 为 true 时返回 true否则 false-- ---------------------------------------------------------------------------localfunctiondefault_compare(a,b)returnabend-- ----------------------------------------------------------------------------- 计算内省排序最大递归深度2 * floor(log2(n))-- 说明理想平衡快排每层把区间减半递归深度近似 log2(n)-- 乘以因子 2 给快排预留两倍犯错余量超过即认定病态切堆排序。-- 参数nLength 数组长度1-- 返回递归深度限制-- ---------------------------------------------------------------------------localfunctioncompute_depth_limit(nLength)ifnLength1thenreturnINTROSORT_MIN_DEPTHendlocalnDepth0localnTempnLengthwhilenTemp1donTempmath_floor(nTemp/2)nDepthnDepth1endreturnINTROSORT_DEPTH_FACTOR*nDepthend-- ----------------------------------------------------------------------------- 公开接口内省排序复刻标准库 table.sort 语义-- 参数tArr 数组连续整数键元素个数以 #tArr 判定-- fnCompare 可选比较器 function(a, b) - boolean-- 返回无原地排序-- 说明fnCompare 缺省时按 升序排序-- 空表与单元素表直接返回-- 与 table.sort 一致要求 tArr 必须是连续数组且元素可比较。-- ---------------------------------------------------------------------------functionSmallgame_IntroSort(tArr,fnCompare)localnLength#tArrifnLength1thenreturnendlocalfnCmpfnCompareiffnCmpnilthenfnCmpdefault_compareend-- 计算最大递归深度然后在整个数组上执行内省排序introsort_impl(tArr,1,nLength,compute_depth_limit(nLength),fnCmp)end-- ----------------------------------------------------------------------------- 自检测试验证 Smallgame_IntroSort 与标准库 table.sort 行为一致-- 说明仅供开发/回归自检使用生产路径禁止调用不注册任何回调与事件。-- 用法Smallgame_IntroSort_SelfTest() 调用完成返回布尔 bAllPass-- 任一断言失败打印 [INTROSORT_SELF_TEST] FAIL 原因 并继续-- 全部通过打印 [INTROSORT_SELF_TEST] PASS。-- 覆盖用例对照全部以 table.sort 结果为准-- 1) 空表 2) 单元素 3) 双元素 4) 已有序 5) 逆序-- 6) 大量重复 7) 字符串 8) 自定义升序 9) 自定义比较器反序-- 10) 对象多键 11) 随机大数组 12) 深度耗尽病态堆排序兜底-- ---------------------------------------------------------------------------functionSmallgame_IntroSort_SelfTest()localnFailed0-- 失败断言计数localnPassed0-- 通过断言计数-- 本地解析引用性能与热更新无副作用localtable_sorttable.sort-- 标准库对照localfunctionclone_array(tSrc)-- 深拷贝数组值拷贝localtDst{}fornIndex1,#tSrcdotDst[nIndex]tSrc[nIndex]endreturntDstend-- 单个断言二者数组逐元素相等localfunctionassert_array_equal(tLhs,tRhs,szCaseName)if#tLhs~#tRhsthennFailednFailed1print([INTROSORT_SELF_TEST] FAIL ..szCaseName.. length ..tostring(#tLhs).. ! ..tostring(#tRhs))returnendfornIndex1,#tLhsdoiftLhs[nIndex]~tRhs[nIndex]thennFailednFailed1print([INTROSORT_SELF_TEST] FAIL ..szCaseName.. index ..tostring(nIndex).. got ..tostring(tLhs[nIndex]).. want ..tostring(tRhs[nIndex]))returnendendnPassednPassed1end-- 用例给定源数组与比较器分别用本实现与标准库排序后再对照localfunctionrun_case(tSrc,szCaseName,fnCompare)localtMineclone_array(tSrc)localtStdclone_array(tSrc)Smallgame_IntroSort(tMine,fnCompare)table_sort(tStd,fnCompare)assert_array_equal(tMine,tStd,szCaseName)end-- 1) 空表不动数组、不抛错dolocaltEmpty{}Smallgame_IntroSort(tEmpty)if#tEmpty0thennPassednPassed1elsenFailednFailed1print([INTROSORT_SELF_TEST] FAIL empty case length ..tostring(#tEmpty))endend-- 2) 单元素不动数组run_case({42},single)-- 3) 双元素run_case({2,1},two)-- 4) 已有序含重复run_case({1,2,3,4,5},ascending)run_case({1,1,2,2,3},ascending_dup)-- 5) 逆序run_case({5,4,3,2,1},descending)-- 6) 大量重复run_case({3,3,3,3,3},all_dup)run_case({2,1,2,1,2,1},mixin_dup)-- 7) 字符串run_case({pear,apple,banana,cherry},strings)-- 8) 自定义升序比较器与原 语义一致的显式比较器localfunctioncmp_asc(a,b)returnabendrun_case({9,3,7,1,5},custom_asc,cmp_asc)-- 9) 自定义比较器按降序localfunctioncmp_desc(a,b)returnabendrun_case({1,9,3,7,5},custom_desc,cmp_desc)-- 10) 对象多键比较器按 nKey 升序、同键按 nSeqlocalfunctioncmp_multi(a,b)ifa.nKey~b.nKeythenreturna.nKeyb.nKeyendreturna.nSeqb.nSeqendlocaltObjects{{nKey3,nSeq2},{nKey1,nSeq9},{nKey2,nSeq5},{nKey3,nSeq1},{nKey1,nSeq2},{nKey2,nSeq1},}run_case(tObjects,object_multi,cmp_multi)-- 11) 随机大数组默认比较器与自定义比较器各若干轮localnSeed20260930-- 固定种子保证可复现localfunctionrand_int(nLow,nHigh)nSeed(nSeed*110351524512345)%2147483648returnnLow(nSeed%(nHigh-nLow1))endfornRound1,8dolocaltRandom{}localnLengthrand_int(0,300)fornIndex1,nLengthdotRandom[nIndex]rand_int(-1000,1000)endrun_case(tRandom,random_..tostring(nRound))endfornRound1,4dolocaltRandDesc{}localnLengthrand_int(0,200)fornIndex1,nLengthdotRandDesc[nIndex]rand_int(1,50)endrun_case(tRandDesc,random_desc_..tostring(nRound),cmp_desc)end-- 12) 病态输入使内省排序递归深度超限触发堆排序兜底-- 构造 2^14 量级元素且取中值恰为区间极值的输入迫使深度耗尽localnBig2^14localtAdversarial{}fornIndex1,nBigdotAdversarial[nIndex]nIndexendrun_case(tAdversarial,adversarial_sorted,cmp_desc)localtAdversarial2{}fornIndex1,nBigdotAdversarial2[nIndex]nBig-nIndex1endrun_case(tAdversarial2,adversarial_reverse,cmp_desc)-- 收尾ifnFailed0thenprint([INTROSORT_SELF_TEST] PASS count..tostring(nPassed))returntrueendprint([INTROSORT_SELF_TEST] FAIL count failed..tostring(nFailed).. passed..tostring(nPassed))returnfalseend-- -- 说明本文件暴露 Smallgame_IntroSort 供麻将/畅玩阁/小游戏统一调用-- 另暴露 Smallgame_IntroSort_SelfTest 自检测试函数仅供开发/回归自检。-- 模块表由引擎按 modulelist.xml 登记聚合。-- Smallgame_IntroSort_SelfTest() 内省排序（lua:Introsort）
-- -- 内省排序Introsort实现模块-- 功能提供复刻标准库 table.sort 语义的内省排序接口-- 供麻将、畅玩阁、小游戏统一调用保证排序效率与最坏复杂度。-- 使用local module_smallgame Include(modules/smallgame)-- module_smallgame.Smallgame_IntroSort(tArr, fnCompare)-- -- 算法结构-- 1. 快速排序三点取中选枢轴 单次划分递归排序正常路径-- 2. 递归深度超限2 * floor(log2(n))时切换为堆排序兜底-- 保证最坏时间复杂度 O(n log n)-- 3. 区间长度不超过 16 时改用插入排序收尾小数组常数极小。-- 语义对齐标准库 table.sort-- - tArr 必须为连续整数键数组1..#tArr原地排序-- - fnCompare(a, b) 返回布尔表示 a 应排在 b 之前缺省用 比较-- - 空表与单元素表直接返回不做任何处理。-- -- 局部化系统库函数热更新不影响提高性能localtypetype-- 获取类型localpairspairs-- 遍历键值对localmath_floormath.floor-- 向下取整localmath_minmath.min-- 取最小值localmath_maxmath.max-- 取最大值localtable_inserttable.insert-- 向表中插入元素localtable_removetable.remove-- 删除表中指定位置的元素-- 插入排序阈值区间长度不超过该值时使用插入排序localINTROSORT_INSERTION_THRESHOLD16-- 深度系数递归深度限制 2 * floor(log2(n))与标准内省排序一致localINTROSORT_DEPTH_FACTOR2-- 深度下限长度不满 2 的区间直接使用插入排序无需进行对数计算localINTROSORT_MIN_DEPTH0-- ----------------------------------------------------------------------------- 插入排序对数组 tArr 的 [nLeft, nRight] 区间做插入排序-- 说明小数组上常数因子小优于快速排序顺带作为内省排序的收尾器。-- 参数tArr 数组nLeft 左边界nRight 右边界含fnCompare 比较器-- ---------------------------------------------------------------------------localfunctioninsertion_sort(tArr,nLeft,nRight,fnCompare)fornIndexnLeft1,nRightdolocaltValuetArr[nIndex]-- 取出待插入元素localnPosnIndex-1-- 从当前元素前一个位置向前扫描whilenPosnLeftandfnCompare(tValue,tArr[nPos])dotArr[nPos1]tArr[nPos]-- 比待插入元素大的整体右移一格nPosnPos-1endtArr[nPos1]tValue-- 待插入元素落入正确位置endend-- ----------------------------------------------------------------------------- 三点取中返回 tArr[nLeft]、tArr[nMid]、tArr[nRight] 三者中位数的下标-- 目的避免取到区间最小/最大元素而退化成倾斜分区-- 对已有序/逆序输入第一趟即可切到中位。-- 参数fnCompare 比较器返回 true 表示前一个参数应排在后面参数之前-- ---------------------------------------------------------------------------localfunctionmedian_of_three(tArr,nLeft,nMid,nRight,fnCompare)-- 处理 nLeft 与 nMid 的比较结果iffnCompare(tArr[nMid],tArr[nLeft])then-- nMid nLeftiffnCompare(tArr[nRight],tArr[nLeft])then-- nMid nRight nLeft中位数为 nRightiffnCompare(tArr[nMid],tArr[nRight])thenreturnnRightelsereturnnMidendelse-- nMid nLeft nRight中位数为 nLeftreturnnLeftendelse-- nLeft nMidiffnCompare(tArr[nRight],tArr[nMid])then-- nRight nMidiffnCompare(tArr[nRight],tArr[nLeft])then-- nRight nLeft nMid中位数为 nLeftreturnnLeftelsereturnnRightendelse-- nLeft nMid nRight中位数为 nMidreturnnMidendendend-- ----------------------------------------------------------------------------- 快速排序单次划分Lomuto 模式-- 说明以枢轴为分界左侧元素全部 枢轴右侧元素全部 枢轴-- 返回枢轴最终落位下标。枢轴值先取出存放到局部变量-- 避免元素交换时枢轴被改写防止比较基准漂移。-- 参数tArr 数组nLeft 左边界nRight 右边界含fnCompare 比较器-- 返回枢轴最终下标 nPivot-- ---------------------------------------------------------------------------localfunctionpartition(tArr,nLeft,nRight,fnCompare)localnMidnLeftmath_floor((nRight-nLeft)/2)-- 中点下标localnPivotIndexmedian_of_three(tArr,nLeft,nMid,nRight,fnCompare)localtPivottArr[nPivotIndex]-- 取出枢轴值-- 将枢轴临时移到区间末尾便于单向扫描tArr[nPivotIndex]tArr[nRight]tArr[nRight]tPivotlocalnStorenLeft-- 小元素放置区边界fornIndexnLeft,nRight-1doiffnCompare(tArr[nIndex],tPivot)then-- 小于枢轴归左区localtTemptArr[nIndex]tArr[nIndex]tArr[nStore]tArr[nStore]tTemp nStorenStore1endend-- 枢轴放回分界处tArr[nRight]tArr[nStore]tArr[nStore]tPivotreturnnStoreend-- ----------------------------------------------------------------------------- 堆排序对数组 tArr 的 [nLeft, nRight] 区间做堆排序递归深度超限兜底-- 说明原地建最大堆 逐次取出堆顶放末尾最坏 O(n log n)、O(1) 额外空间。-- 参数tArr 数组nLeft 左边界nRight 右边界含fnCompare 比较器-- ---------------------------------------------------------------------------localfunctionsift_down(tArr,nLeft,nRange,nRoot,fnCompare)localnLargestnRootlocalnLeftChildnLeft(nRoot-nLeft)*21-- 左子下标localnRightChildnLeftChild1-- 右子下标ifnLeftChildnRangeandfnCompare(tArr[nLargest],tArr[nLeftChild])thennLargestnLeftChildendifnRightChildnRangeandfnCompare(tArr[nLargest],tArr[nRightChild])thennLargestnRightChildendifnLargest~nRootthenlocaltTemptArr[nLargest]tArr[nLargest]tArr[nRoot]tArr[nRoot]tTempsift_down(tArr,nLeft,nRange,nLargest,fnCompare)endendlocalfunctionheap_sort(tArr,nLeft,nRight,fnCompare)localnRangenRight-- 当前堆的右边界-- 建堆从最后一个非叶子结点开始自底向上调整fornIndexmath_floor((nRange-nLeft)/2),0,-1dosift_down(tArr,nLeft,nRange,nLeftnIndex,fnCompare)end-- 依次取出堆顶最大元素放到末尾然后重新调整剩余部分fornIndexnRange,nLeft1,-1dolocaltTemptArr[nLeft]tArr[nLeft]tArr[nIndex]tArr[nIndex]tTempsift_down(tArr,nLeft,nIndex-1,nLeft,fnCompare)endend-- ----------------------------------------------------------------------------- 内省排序主流程递归版-- 说明深度超限时切堆排序兜底深度未超限且区间大于阈值时快排划分-- 区间收窄到阈值内时切插入排序收尾。-- 参数tArr 数组nLeft 左边界nRight 右边界含-- nDepth 剩余递归深度fnCompare 比较器-- ---------------------------------------------------------------------------localfunctionintrosort_impl(tArr,nLeft,nRight,nDepth,fnCompare)whilenRight-nLeft1INTROSORT_INSERTION_THRESHOLDdoifnDepthINTROSORT_MIN_DEPTHthen-- 递归深度超限判定输入病态整段堆排序兜底并结束heap_sort(tArr,nLeft,nRight,fnCompare)returnendnDepthnDepth-1localnPivotpartition(tArr,nLeft,nRight,fnCompare)-- 递归处理右半区不含枢轴左半区交给外层循环继续迭代introsort_impl(tArr,nPivot1,nRight,nDepth,fnCompare)nRightnPivot-1end-- 区间长度收窄到阈值内插入排序收尾insertion_sort(tArr,nLeft,nRight,fnCompare)end-- ----------------------------------------------------------------------------- 默认比较器升序等价于标准库 table.sort 缺省 比较-- 参数a 任意可比值b 任意可比值-- 返回a b 为 true 时返回 true否则 false-- ---------------------------------------------------------------------------localfunctiondefault_compare(a,b)returnabend-- ----------------------------------------------------------------------------- 计算内省排序最大递归深度2 * floor(log2(n))-- 说明理想平衡快排每层把区间减半递归深度近似 log2(n)-- 乘以因子 2 给快排预留两倍犯错余量超过即认定病态切堆排序。-- 参数nLength 数组长度1-- 返回递归深度限制-- ---------------------------------------------------------------------------localfunctioncompute_depth_limit(nLength)ifnLength1thenreturnINTROSORT_MIN_DEPTHendlocalnDepth0localnTempnLengthwhilenTemp1donTempmath_floor(nTemp/2)nDepthnDepth1endreturnINTROSORT_DEPTH_FACTOR*nDepthend-- ----------------------------------------------------------------------------- 公开接口内省排序复刻标准库 table.sort 语义-- 参数tArr 数组连续整数键元素个数以 #tArr 判定-- fnCompare 可选比较器 function(a, b) - boolean-- 返回无原地排序-- 说明fnCompare 缺省时按 升序排序-- 空表与单元素表直接返回-- 与 table.sort 一致要求 tArr 必须是连续数组且元素可比较。-- ---------------------------------------------------------------------------functionSmallgame_IntroSort(tArr,fnCompare)localnLength#tArrifnLength1thenreturnendlocalfnCmpfnCompareiffnCmpnilthenfnCmpdefault_compareend-- 计算最大递归深度然后在整个数组上执行内省排序introsort_impl(tArr,1,nLength,compute_depth_limit(nLength),fnCmp)end-- ----------------------------------------------------------------------------- 自检测试验证 Smallgame_IntroSort 与标准库 table.sort 行为一致-- 说明仅供开发/回归自检使用生产路径禁止调用不注册任何回调与事件。-- 用法Smallgame_IntroSort_SelfTest() 调用完成返回布尔 bAllPass-- 任一断言失败打印 [INTROSORT_SELF_TEST] FAIL 原因 并继续-- 全部通过打印 [INTROSORT_SELF_TEST] PASS。-- 覆盖用例对照全部以 table.sort 结果为准-- 1) 空表 2) 单元素 3) 双元素 4) 已有序 5) 逆序-- 6) 大量重复 7) 字符串 8) 自定义升序 9) 自定义比较器反序-- 10) 对象多键 11) 随机大数组 12) 深度耗尽病态堆排序兜底-- ---------------------------------------------------------------------------functionSmallgame_IntroSort_SelfTest()localnFailed0-- 失败断言计数localnPassed0-- 通过断言计数-- 本地解析引用性能与热更新无副作用localtable_sorttable.sort-- 标准库对照localfunctionclone_array(tSrc)-- 深拷贝数组值拷贝localtDst{}fornIndex1,#tSrcdotDst[nIndex]tSrc[nIndex]endreturntDstend-- 单个断言二者数组逐元素相等localfunctionassert_array_equal(tLhs,tRhs,szCaseName)if#tLhs~#tRhsthennFailednFailed1print([INTROSORT_SELF_TEST] FAIL ..szCaseName.. length ..tostring(#tLhs).. ! ..tostring(#tRhs))returnendfornIndex1,#tLhsdoiftLhs[nIndex]~tRhs[nIndex]thennFailednFailed1print([INTROSORT_SELF_TEST] FAIL ..szCaseName.. index ..tostring(nIndex).. got ..tostring(tLhs[nIndex]).. want ..tostring(tRhs[nIndex]))returnendendnPassednPassed1end-- 用例给定源数组与比较器分别用本实现与标准库排序后再对照localfunctionrun_case(tSrc,szCaseName,fnCompare)localtMineclone_array(tSrc)localtStdclone_array(tSrc)Smallgame_IntroSort(tMine,fnCompare)table_sort(tStd,fnCompare)assert_array_equal(tMine,tStd,szCaseName)end-- 1) 空表不动数组、不抛错dolocaltEmpty{}Smallgame_IntroSort(tEmpty)if#tEmpty0thennPassednPassed1elsenFailednFailed1print([INTROSORT_SELF_TEST] FAIL empty case length ..tostring(#tEmpty))endend-- 2) 单元素不动数组run_case({42},single)-- 3) 双元素run_case({2,1},two)-- 4) 已有序含重复run_case({1,2,3,4,5},ascending)run_case({1,1,2,2,3},ascending_dup)-- 5) 逆序run_case({5,4,3,2,1},descending)-- 6) 大量重复run_case({3,3,3,3,3},all_dup)run_case({2,1,2,1,2,1},mixin_dup)-- 7) 字符串run_case({pear,apple,banana,cherry},strings)-- 8) 自定义升序比较器与原 语义一致的显式比较器localfunctioncmp_asc(a,b)returnabendrun_case({9,3,7,1,5},custom_asc,cmp_asc)-- 9) 自定义比较器按降序localfunctioncmp_desc(a,b)returnabendrun_case({1,9,3,7,5},custom_desc,cmp_desc)-- 10) 对象多键比较器按 nKey 升序、同键按 nSeqlocalfunctioncmp_multi(a,b)ifa.nKey~b.nKeythenreturna.nKeyb.nKeyendreturna.nSeqb.nSeqendlocaltObjects{{nKey3,nSeq2},{nKey1,nSeq9},{nKey2,nSeq5},{nKey3,nSeq1},{nKey1,nSeq2},{nKey2,nSeq1},}run_case(tObjects,object_multi,cmp_multi)-- 11) 随机大数组默认比较器与自定义比较器各若干轮localnSeed20260930-- 固定种子保证可复现localfunctionrand_int(nLow,nHigh)nSeed(nSeed*110351524512345)%2147483648returnnLow(nSeed%(nHigh-nLow1))endfornRound1,8dolocaltRandom{}localnLengthrand_int(0,300)fornIndex1,nLengthdotRandom[nIndex]rand_int(-1000,1000)endrun_case(tRandom,random_..tostring(nRound))endfornRound1,4dolocaltRandDesc{}localnLengthrand_int(0,200)fornIndex1,nLengthdotRandDesc[nIndex]rand_int(1,50)endrun_case(tRandDesc,random_desc_..tostring(nRound),cmp_desc)end-- 12) 病态输入使内省排序递归深度超限触发堆排序兜底-- 构造 2^14 量级元素且取中值恰为区间极值的输入迫使深度耗尽localnBig2^14localtAdversarial{}fornIndex1,nBigdotAdversarial[nIndex]nIndexendrun_case(tAdversarial,adversarial_sorted,cmp_desc)localtAdversarial2{}fornIndex1,nBigdotAdversarial2[nIndex]nBig-nIndex1endrun_case(tAdversarial2,adversarial_reverse,cmp_desc)-- 收尾ifnFailed0thenprint([INTROSORT_SELF_TEST] PASS count..tostring(nPassed))returntrueendprint([INTROSORT_SELF_TEST] FAIL count failed..tostring(nFailed).. passed..tostring(nPassed))returnfalseend-- -- 说明本文件暴露 Smallgame_IntroSort 供麻将/畅玩阁/小游戏统一调用-- 另暴露 Smallgame_IntroSort_SelfTest 自检测试函数仅供开发/回归自检。-- 模块表由引擎按 modulelist.xml 登记聚合。-- Smallgame_IntroSort_SelfTest()