编程语言语言运行时标准库垃圾回收并发编程【免费下载链接】cangjie_runtime仓颉编程语言运行时与标准库。项目地址https://gitcode.com/Cangjie/cangjie_runtime点击查看免费下载导读本文面向使用仓颉Cangjie语言进行开发的工程师系统讲解标准库 std.sort 包 的完整能力它提供了针对Array、ArrayList、List三类容器的泛型排序函数支持稳定/不稳定排序、升序/降序四种组合并支持基于ComparableT接口、Ordering比较器、Bool谓词和键映射函数四种比较策略。读完本文你将能够熟练选择并正确调用每一组sort重载理解比较函数必须满足的全序契约并从源码层面掌握底层 timSort稳定与 introSort不稳定两种算法及基本类型快速路径的加速机制。std.sort 包功能概览std.sort包为数组类型提供排序函数其核心设计包含三个维度排序稳定性提供稳定排序与不稳定排序两套实现。稳定排序保证相等元素的前后顺序在排序前后保持不变不稳定排序则不保证这一点。泛型支持提供一组泛型排序函数可对元素类型为T的数组排序。由于排序必然要求元素可比较这些函数被分为两类要求T实现ComparableT接口直接利用类型自带的compare语义由调用方把T相关的比较函数作为参数传入比较逻辑与类型解耦适用于不便修改类型定义或需要临时指定不同排序规则的场景。辅助接口提供SortByExtension与SortExtension两个辅助接口用于为其他类型扩展排序相关函数。需要说明的是这两个接口及stableSort、unstableSort系列函数均已被标注为“未来版本即将废弃deprecated”官方推荐统一迁移到新的sort函数族。包的源码实现位于 stdlib/libs/std/sort 目录由sort.cj、stable_sort.cj、unstable_sort.cj、sort_util.cj与primitive_sort_fast_paths.cj五个源文件组成见 CMakeLists.txt其中stable_sort.cj对应稳定排序算法unstable_sort.cj对应不稳定排序算法下文将逐一展开。排序函数族三种容器 × 四种比较策略sort函数是一族重载覆盖ArrayT、ArrayListT、ListT三种容器每种容器又支持四种比较策略共 12 个函数。四类比较策略分别是比较策略签名特征适用场景接口约束sortT(data, stable, descending) where T : ComparableT元素类型已实现ComparableT最简洁Ordering 比较器sortT(data, by!, stable, descending)需要精细的三态比较小于/等于/大于可自定义规则Bool 谓词sortT(data, lessThan!, stable, descending)只需回答“t1 是否应排在 t2 前”的简单场景键映射sortT, K(data, key!, stable, descending) where K : ComparableK按元素某个派生键排序如对象某字段所有函数的参数均为命名参数参数名后带!表示可省略命名参数名。三个容器的排序函数之间并非独立实现从源码 sort.cj 可以看到ListT版本通过toArray()转为数组排序后再回填data.clear()后重新addArrayListT版本则通过unsafe块调用getRawArray()直接对底层数组切片排序后调用updateVersion()更新版本号而真正的排序算法最终都落在ArrayT上因此理解Array版本的语义即可掌握全部。1. Comparable 约束版本sortT(data, stable, descending) where T : ComparableTpublic func sortT(data: ArrayT, stable!: Bool false, descending!: Bool false): Unit where T : ComparableT适用于T已实现ComparableT接口的类型。从 sort.cj 的实现可见降序时通过{l: T, r: T r.compare(l)}反转比较方向然后按stable标志分派到stableSort或unstableSort。示例Rectangle实现ComparableRectangle按面积降序稳定排序import std.sort.* class Rectangle : ComparableRectangle ToString { var width: Int64 var height: Int64 public init(width: Int64, height: Int64) { this.width width this.height height } public func compare(r: Rectangle) { let tValue: Int64 this.width * this.height let rValue: Int64 r.width * r.height if (tValue rValue) { return Ordering.GT } else if (tValue rValue) { return Ordering.EQ } else { return Ordering.LT } } public func toString(): String { return #width: ${this.width}, height: ${this.height} } } main() { /* 按照面积降序排序 */ var arr [Rectangle(4, 8), Rectangle(6, 7), Rectangle(2, 6)] sortRectangle(arr, stable: true, descending: true) println(arr) return 0 }运行结果[#width: 6, height: 7, #width: 4, height: 8, #width: 2, height: 6]2. Ordering 比较器版本sortT(data, by!, stable, descending)public func sortT(data: ArrayT, by!: (T, T) - Ordering, stable!: Bool false, descending!: Bool false): Unit用户传入返回 Ordering 的比较函数by。Ordering是std.core中的三值枚举LT / GT / EQ语义为by(t1, t2)返回GT排序后t1在t2后返回LT排序后t1在t2前返回EQt1与t2的前后位置与是否稳定排序有关——稳定则保持排序前的相对顺序不稳定则可能发生改变。降序实现见 sort.cj通过match将GT↔LT互换、EQ保持不变后重新包装比较器。示例按面积降序排序import std.sort.* class Rectangle : ToString { var width: Int64 var height: Int64 public init(width: Int64, height: Int64) { this.width width this.height height } public func toString(): String { return #width: ${this.width}, height: ${this.height} } } main() { /* 按照面积降序排序 */ var arr [Rectangle(4, 8), Rectangle(6, 7), Rectangle(2, 6)] sortRectangle( arr, by: { r1: Rectangle, r2: Rectangle let r1Value: Int64 r1.width * r1.height let r2Value: Int64 r2.width * r2.height if (r1Value r2Value) { return Ordering.GT } else if (r1Value r2Value) { return Ordering.EQ } else { return Ordering.LT } }, stable: true, descending: true ) println(arr) return 0 }运行结果[#width: 6, height: 7, #width: 4, height: 8, #width: 2, height: 6]3. Bool 谓词版本sortT(data, lessThan!, stable, descending)public func sortT(data: ArrayT, lessThan!: (T, T) - Bool, stable!: Bool false, descending!: Bool false): Unit用户传入返回Bool的比较函数lessThan语义约定lessThan(t1, t2)返回true排序后t1在t2前返回false时需区分两种情况若t1与t2不相等排序后t1在t2后若二者相等则前后位置与稳定性相关稳定则保持不变不稳定则可能改变。注意 sort.cj 的实现它通过match (lessThan(l, r))并借助反向调用lessThan(r, l)将Bool谓词转换为Ordering比较器true → LT反向为true → GT否则EQ再复用 Ordering 版本排序。示例按面积降序排序import std.sort.* class Rectangle : ToString { var width: Int64 var height: Int64 public init(width: Int64, height: Int64) { this.width width this.height height } public func toString(): String { return #width: ${this.width}, height: ${this.height} } } main() { /* 按照面积降序排序 */ var arr [Rectangle(4, 8), Rectangle(6, 7), Rectangle(2, 6)] sortRectangle( arr, lessThan: { r1: Rectangle, r2: Rectangle let r1Value: Int64 r1.width * r1.height let r2Value: Int64 r2.width * r2.height return r1Value r2Value }, stable: true, descending: true ) println(arr) return 0 }运行结果[#width: 6, height: 7, #width: 4, height: 8, #width: 2, height: 6]4. 键映射版本sortT, K(data, key!, stable, descending) where K : ComparableKpublic func sortT, K(data: ArrayT, key!: (T) - K, stable!: Bool false, descending!: Bool false): Unit where K : ComparableK用户传入“元素 → 键”的映射函数key键类型K需实现ComparableK。这是最贴合“按对象某个字段排序”需求的写法。从 sort.cj 的实现可见升序比较器为key(l).compare(key(r))降序则交换为key(r).compare(key(l))。示例Rectangle无需实现Comparable直接按width字段降序稳定排序import std.sort.* class Rectangle : ToString { var width: Int64 var height: Int64 public init(width: Int64, height: Int64) { this.width width this.height height } public func toString(): String { return #width: ${this.width}, height: ${this.height} } } main() { /* 按照宽降序排序 */ var arr [Rectangle(4, 8), Rectangle(6, 7), Rectangle(2, 6)] sortRectangle, Int64( arr, key: { r: Rectangle return r.width }, stable: true, descending: true ) println(arr) return 0 }运行结果[#width: 6, height: 7, #width: 4, height: 8, #width: 2, height: 6]ArrayList 与 List 版本ArrayListT与ListT分别拥有与ArrayT完全对应的四类重载签名与语义一致仅容器类型不同sortT(data: ArrayListT, ...)/sortT(data: ListT, ...)见 sort_package_funcs.mdArrayListT完整签名示例如public func sortT(data: ArrayListT, by!: (T, T) - Ordering, stable!: Bool false, descending!: Bool false): Unit底层通过getRawArray()直接操作底层数组并updateVersion()效率最高ListT版本则通过toArray()→ 排序 →clear()→ 回填的方式完成适用于任何List实现类。比较函数契约必须满足全序关系无论使用by、lessThan还是compare传入的比较函数都必须满足全序关系的以下三条要求源码 sort.cj 与官方文档均明确声明性质Ordering形式Bool形式反对称性若compare(a, b)为LT则compare(b, a)必须为GT若lessThan(a, b)为true则lessThan(b, a)必须为false传递性若compare(a, b)为LT且compare(b, c)为LT则compare(a, c)必须为LT若lessThan(a, b)和lessThan(b, c)均为true则lessThan(a, c)必须为true一致性多次调用compare(a, b)必须返回相同结果多次调用lessThan(a, b)必须返回相同结果违反上述要求可能导致未定义行为——例如返回结果随调用次数变化的比较器会破坏算法内部的运行检测、归并决策与分区逻辑产生错误顺序甚至越界等风险。请确保比较器是纯函数无副作用、无状态依赖。源码级实现剖析timSort 与 introSortstd.sort的稳定性差异在算法层面体现得非常清晰这也有助于理解为什么稳定排序通常需要额外的临时空间。稳定排序timSortstable_sort.cj当stable: true时排序最终走data.timSort()见 stable_sort.cj小数组短路size 64时直接调用shortSort——长度 ≤ 8 用插入排序 / 三元比较交换compareSwap3否则先探测自然有序段再二分插入排序自然段探测getSequenceLength识别数组中的升序/降序段descending run 会被翻转处理显著利用已有有序性minRun 截断getMinRunLength()计算目标 run 长度n 64时逐位右移累积见 sort_util.cj不足时用二分插入排序补齐run 栈与归并maybeMerge维护栈不变量每个 run 严格长于其上两个 run 长度之和呈斐波那契式递减栈容量按1.5 * log2(size) 8预留归并时先用queryLT/queryGT裁剪两端无需移动的元素再根据左右段长度选择mergeFromLeft或mergeFromRight并配合 galloping步长倍增快速跳过连续胜出段临时数组TempArray按runSize 1上限按需扩容复用归并只拷贝较短一侧空间效率接近原地。不稳定排序introSortunstable_sort.cj当stable: false时排序最终走data.introSort()见 unstable_sort.cj即“内省排序”——快排 堆排 插入排序的混合策略深度限制depth()预计算递归深度上限2 * log2(size)一旦快排递归深度耗尽d 0立即切换heapSort杜绝最坏 O(n²) 退化分区selectPartitionPivot对长度 ≥ 64 的区间采样 5 个点begin、beginoff、mid、midoff、end做三值取中getPartition采用荷兰国旗式三向分区将大量与 pivot 相等的元素集中到中间同时返回(lo, hi)边界小数组短路len 16时落入直接交换/插入排序递归与循环结合源码注释明确“Let the smaller side do recursion, Let the bigger side do loop”即对较小的一侧递归、较大的一侧迭代控制栈深度进入算法前unstable_sort.cj 还会先检查整体是否已升序/降序——已升序直接返回已降序直接reverseRange翻转两个 O(n) 检查常常能免去整个排序过程。基本类型快速路径primitive_sort_fast_paths.cj对Int8/Int16/Int32/Int64/IntNative、UInt8...UIntNative、Float16/Float32/Float64、Rune等基本数值类型sort会先尝试类型判断data as ArrayInt64等命中后直接调用对应的专用排序入口见 primitive_sort_fast_paths.cj从而绕开泛型比较的间接调用开销这是仓颉std.sort为常见数值场景内置的显式性能优化路径。综合实战对 Array 与 List 排序以下示例来自 sort_samples/sort_sample_array.md覆盖了四种比较策略在同一容器上的组合用法可直接编译运行验证import std.sort.* class Student : ToString { public var name: String public var age: Int64 public init(name: String, age: Int64) { this.name name this.age age } public func toString(): String { return {name: ${name} age: ${age}} } } main() { // 对 Int64 数组升序排序 var numbers [1, 3, 5, 2, 4] sort(numbers) println(numbers) // 通过比较器按照年龄升序排序 var students [Student(A, 8), Student(B, 7), Student(C, 3), Student(D, 4), Student(E, 6)] let comparator {l: Student, r: Student l.age.compare(r.age)} sort(students, by: comparator) println(students) // 按照年龄降序排序 var studentsDescending [Student(A, 8), Student(B, 7), Student(C, 3), Student(D, 4), Student(E, 6)] let lessThan {l: Student, r: Student l.age r.age} sort(studentsDescending, lessThan: lessThan, descending: true) println(studentsDescending) // 通过键按照年龄升序排序并且是稳定排序 var studentsStable [Student(A, 8), Student(B, 7), Student(C, 7), Student(D, 4), Student(E, 7)] let key {i: Student i.age} sort(studentsStable, key: key, stable: true) println(studentsStable) return 0 }运行结果[1, 2, 3, 4, 5] [{name: C age: 3}, {name: D age: 4}, {name: E age: 6}, {name: B age: 7}, {name: A age: 8}] [{name: A age: 8}, {name: B age: 7}, {name: E age: 6}, {name: D age: 4}, {name: C age: 3}] [{name: D age: 4}, {name: B age: 7}, {name: C age: 7}, {name: E age: 7}, {name: A age: 8}]注意最后一个示例的语义B、C、E三个学生年龄同为 7启用stable: true后它们的相对顺序保持为B → C → E不变若改为stable: false这三个等值元素的先后次序则不被保证。ArrayListT版本的用法完全一致只需将数组字面量替换为ArrayListT([...])或逐条add构造即可完整示例同样见 sort_samples/sort_sample_array.md。已废弃 API迁移到 sort 函数族stableSort / unstableSortstableSort与unstableSort各有两个重载Comparable版本与(T, T) - Ordering版本提供升序排序能力。它们在当前版本中仍可编译使用实现即上文剖析的 timSort 与 introSort 入口但官方已标注deprecated未来版本将废弃请统一迁移废弃函数替代方案stableSortT(ArrayT)sort(data, stable: true)stableSortT(ArrayT, comparator)sort(data, by: comparator, stable: true)unstableSortT(ArrayT)sort(data)unstableSortT(ArrayT, comparator)sort(data, by: comparator)SortByExtension 与 SortExtension 接口SortByExtensionT 提供sortBy(comparator!)与sortBy(stable!, comparator!)其ArrayT扩展实现sortBy内部即调用stableSort/unstableSortSortExtension 提供sort()、sort(stable!)、sortDescending()、sortDescending(stable!)其ArrayTT : ComparableT扩展实现等价于新sort的升/降序 稳定/不稳定组合。两个接口与全部扩展方法均标注 deprecated无替代扩展接口官方建议直接改用对应的全局sort函数。典型旧写法let arr [3, 1, 4, 1, 5] arr.sort() // 旧不稳定升序 arr.sort(stable: true) // 旧稳定升序 arr.sortDescending() // 旧不稳定降序 arr.sortBy(comparator: {a, b ...}) // 旧自定义比较器迁移到新 API 后let arr [3, 1, 4, 1, 5] sort(arr) // 不稳定升序 sort(arr, stable: true) // 稳定升序 sort(arr, descending: true) // 不稳定降序 sort(arr, by: {a, b ...}) // 自定义比较器小结与选型建议能用Comparable就不用比较器类型本身定义了自然顺序如数值、字符串直接sort(data)最简洁且可读性最好按字段排序首选key对象数组按属性排序时key: {o o.field}比手写比较器更不易出错且字段类型自带Comparable即可需要三态语义用by涉及“等于”需要特殊处理如稳定保持次序时使用Ordering比较器简单谓词用lessThan只关心前后关系时可使用但要注意其内部会额外调用一次反向比较来合成Ordering稳定与否的取舍业务上要求等值元素保持原序如多级排序的次级关键字、记录入库顺序时用stable: true只关心值的大小时用默认的stable: false其 introSort 通常更快数值数组放心排序基本数值类型的Array会自动命中快速路径无需额外配置。相关的 API 签名与全部重载示例可继续查阅 sort_package_funcs.md 与 sort_package_interfaces.md。赞分享编程语言语言运行时标准库垃圾回收并发编程【免费下载链接】cangjie_runtime仓颉编程语言运行时与标准库。项目地址https://gitcode.com/Cangjie/cangjie_runtime点击查看免费下载相关推荐仓颉编程语言 std.sort 排序包全解析sort 函数族、稳定排序与自定义比较实战仓颉编程语言 std.sort 排序包全解析sort 函数族、稳定排序与自定义比较实战 导读 std.sort 是仓颉标准库中专门提供排序能力的包覆盖 Ar文档知识库教程OpenHarmony仓颉语言 std.sort 包排序 API 全解析稳定排序、比较函数与泛型排序实战仓颉语言 std.sort 包排序 API 全解析稳定排序、比较函数与泛型排序实战 std.sort 是仓颉标准库中专门为数组类容器提供排序能力的功能包。它针文档知识库教程OpenHarmonyQtScrcpy 完整指南4 步免 Root 跑通安卓投屏让手游上电脑QtScrcpy 完整指南4 步免 Root 跑通安卓投屏让手游上电脑 QtScrcpy 是一款做安卓投屏与双向控制的开源软件它把一个小服务推到手机上运行编程语言语言运行时标准库垃圾回收并发编程上一篇小爱音箱AI升级实操指南用 MiGPT 快速接入 ChatGPT变出你的专属语音助手下一篇gptme与第三方API集成扩展AI能力的无限可能创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考