企业官网建设流程全解析

• 编程语言
• 语言运行时
• 标准库
• 垃圾回收
• 并发编程

导读

本文面向使用仓颉（Cangjie）语言进行开发的工程师，系统讲解标准库 std.sort 包 的完整能力：它提供了针对Array、ArrayList、List三类容器的泛型排序函数，支持稳定/不稳定排序、升序/降序四种组合，并支持基于Comparable<T>接口、Ordering比较器、Bool谓词和键映射函数四种比较策略。读完本文，你将能够熟练选择并正确调用每一组sort重载，理解比较函数必须满足的全序契约，并从源码层面掌握底层 timSort（稳定）与 introSort（不稳定）两种算法及基本类型快速路径的加速机制。

std.sort 包功能概览

std.sort包为数组类型提供排序函数，其核心设计包含三个维度：

1. 排序稳定性：提供稳定排序与不稳定排序两套实现。稳定排序保证相等元素的前后顺序在排序前后保持不变；不稳定排序则不保证这一点。
2. 泛型支持：提供一组泛型排序函数，可对元素类型为T的数组排序。由于排序必然要求元素可比较，这些函数被分为两类：
   • 要求T实现Comparable<T>接口（直接利用类型自带的compare语义）；
   • 由调用方把T相关的比较函数作为参数传入（比较逻辑与类型解耦，适用于不便修改类型定义或需要临时指定不同排序规则的场景）。
3. 辅助接口：提供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函数是一族重载，覆盖Array<T>、ArrayList<T>、List<T>三种容器，每种容器又支持四种比较策略，共 12 个函数。四类比较策略分别是：

所有函数的参数均为命名参数（参数名后带!表示可省略命名参数名）。三个容器的排序函数之间并非独立实现：从源码 sort.cj 可以看到，List<T>版本通过toArray()转为数组排序后再回填（data.clear()后重新add），ArrayList<T>版本则通过unsafe块调用getRawArray()直接对底层数组切片排序后调用updateVersion()更新版本号，而真正的排序算法最终都落在Array<T>上，因此理解Array版本的语义即可掌握全部。

1. Comparable 约束版本：sort<T>(data, stable, descending) where T <: Comparable<T>

public func sort<T>(data: Array<T>, stable!: Bool = false, descending!: Bool = false): Unit where T <: Comparable<T>

适用于T已实现Comparable<T>接口的类型。从 sort.cj 的实现可见，降序时通过{l: T, r: T => r.compare(l)}反转比较方向，然后按stable标志分派到stableSort或unstableSort。

示例（Rectangle实现Comparable<Rectangle>，按面积降序稳定排序）：

import std.sort.* class Rectangle <: Comparable<Rectangle> & 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)] sort<Rectangle>(arr, stable: true, descending: true) println(arr) return 0 }

运行结果：

[#width: 6, height: 7, #width: 4, height: 8, #width: 2, height: 6]

2. Ordering 比较器版本：sort<T>(data, by!, stable, descending)

public func sort<T>(data: Array<T>, 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前；
• 返回EQ：t1与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)] sort<Rectangle>( 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 谓词版本：sort<T>(data, lessThan!, stable, descending)

public func sort<T>(data: Array<T>, 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)] sort<Rectangle>( 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. 键映射版本：sort<T, K>(data, key!, stable, descending) where K <: Comparable<K>

public func sort<T, K>(data: Array<T>, key!: (T) -> K, stable!: Bool = false, descending!: Bool = false): Unit where K <: Comparable<K>

用户传入“元素 → 键”的映射函数key，键类型K需实现Comparable<K>。这是最贴合“按对象某个字段排序”需求的写法。从 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)] sort<Rectangle, 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 版本

ArrayList<T>与List<T>分别拥有与Array<T>完全对应的四类重载，签名与语义一致，仅容器类型不同：

• sort<T>(data: ArrayList<T>, ...)/sort<T>(data: List<T>, ...)，见 sort_package_funcs.md；
• ArrayList<T>完整签名示例如：public func sort<T>(data: ArrayList<T>, by!: (T, T) -> Ordering, stable!: Bool = false, descending!: Bool = false): Unit，底层通过getRawArray()直接操作底层数组并updateVersion()，效率最高；
• List<T>版本则通过toArray()→ 排序 →clear()→ 回填的方式完成，适用于任何List实现类。

比较函数契约：必须满足全序关系

无论使用by、lessThan还是compare，传入的比较函数都必须满足全序关系的以下三条要求（源码 sort.cj 与官方文档均明确声明）：

违反上述要求可能导致未定义行为——例如返回结果随调用次数变化的比较器，会破坏算法内部的运行检测、归并决策与分区逻辑，产生错误顺序甚至越界等风险。请确保比较器是纯函数（无副作用、无状态依赖）。

源码级实现剖析：timSort 与 introSort

std.sort的稳定性差异在算法层面体现得非常清晰，这也有助于理解为什么稳定排序通常需要额外的临时空间。

稳定排序：timSort（stable_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上限按需扩容复用，归并只拷贝较短一侧，空间效率接近原地。

不稳定排序：introSort（unstable_sort.cj）

当stable: false时，排序最终走data.introSort()（见 unstable_sort.cj），即“内省排序”——快排 + 堆排 + 插入排序的混合策略：

• 深度限制：depth()预计算递归深度上限（2 * log2(size)），一旦快排递归深度耗尽（d == 0）立即切换heapSort，杜绝最坏 O(n²) 退化；
• 分区：selectPartitionPivot对长度 ≥ 64 的区间采样 5 个点（begin、begin+off、mid、mid+off、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 Array<Int64>等），命中后直接调用对应的专用排序入口（见 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，这三个等值元素的先后次序则不被保证。ArrayList<T>版本的用法完全一致，只需将数组字面量替换为ArrayList<T>([...])或逐条add构造即可（完整示例同样见 sort_samples/sort_sample_array.md）。

已废弃 API：迁移到 sort 函数族

stableSort / unstableSort

stableSort与unstableSort各有两个重载（Comparable版本与(T, T) -> Ordering版本），提供升序排序能力。它们在当前版本中仍可编译使用（实现即上文剖析的 timSort 与 introSort 入口），但官方已标注deprecated，未来版本将废弃，请统一迁移：

SortByExtension 与 SortExtension 接口

• SortByExtension<T> 提供sortBy(comparator!)与sortBy(stable!, comparator!)，其Array<T>扩展实现sortBy内部即调用stableSort/unstableSort；
• SortExtension 提供sort()、sort(stable!)、sortDescending()、sortDescending(stable!)，其Array<T>（T <: Comparable<T>）扩展实现等价于新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。

• 编程语言
• 语言运行时
• 标准库
• 垃圾回收
• 并发编程