Julia 排序与排序相关函数完全指南：sort / sortperm / searchsorted 与 Ordering 机制深入解析-北京尧图网络

Julia 排序与排序相关函数完全指南sort / sortperm / searchsorted 与 Ordering 机制深入解析【免费下载链接】juliaThe Julia Programming Language项目地址: https://gitcode.com/gh_mirrors/ju/julia本文以 Julia 官方文档 doc/src/base/sort.md 为核心骨架结合 Julia 仓库内排序系统的真实实现源码base/sort.jl 与 base/ordering.jl展开系统讲解 Julia 的排序 API、排序算法选型机制、有序数组上的二分查找函数以及可扩展的Ordering排序序抽象。读完本文你将掌握sort/sort!/sortperm/partialsort/sortslices的全部关键字用法理解InsertionSort、MergeSort、QuickSort、PartialQuickSort四类公开算法的适用场景与默认混合策略的工作原理并能够为自定义类型定制专属的排序算法与排序序。快速上手从 sort 到 sort! 的基础用法Julia 为排序提供了广泛、灵活的 API。默认情况下Julia 会挑选合理的算法并按升序排序julia sort([2,3,1]) 3-element Vector{Int64}: 1 2 3传入revtrue即可降序排序julia sort([2,3,1], revtrue) 3-element Vector{Int64}: 3 2 1sort会构造一个排序后的副本保持输入数组不变而带!的爆炸版本会原地修改已有数组julia a [2,3,1]; julia sort!(a); julia a 3-element Vector{Int64}: 1 2 3两者在源码层面的关系非常直接sort(v::AbstractVector; kws...) sort!(copymutable(v); kws...)即先复制再调用sort!见 base/sort.jl#L1780。此外sort还支持对字典的keys/values先收集再排序COLLECT_ON_SORT_TYPES以及从 Julia 1.12 起对NTuple直接排序见 base/sort.jl#L1785-L1808。除了直接对数组排序还可以计算一个让数组变为有序的索引排列julia v [0.297288, 0.382396, -0.597634, -0.0104452, -0.839027] 5-element Vector{Float64}: 0.297288 0.382396 -0.597634 -0.0104452 -0.839027 julia p sortperm(v) 5-element Vector{Int64}: 5 3 4 1 2 julia v[p] 5-element Vector{Float64}: -0.839027 -0.597634 -0.0104452 0.297288 0.382396数组可以按照其元素的任意变换结果进行排序例如按绝对值julia sort(v, byabs) 5-element Vector{Float64}: -0.0104452 0.297288 0.382396 -0.597634 -0.839027也可以按变换结果降序排序julia sort(v, byabs, revtrue) 5-element Vector{Float64}: -0.839027 -0.597634 0.382396 0.297288 -0.0104452需要时还可以显式指定排序算法julia sort(v, algInsertionSort) 5-element Vector{Float64}: -0.839027 -0.597634 -0.0104452 0.297288 0.382396比较语义严格弱序与 lt 关键字所有排序与有序相关函数都依赖一个定义在待排序元素上的小于关系即严格弱序strict weak order。默认调用isless函数但可以通过lt关键字指定其他比较函数——lt接收两个数组元素当且仅当第一个参数小于第二个时返回true。sort!的文档见 base/sort.jl#L1626-L1741对lt提出了严格的数学要求它必须是一个严格弱序即满足非自反性irreflexivelt(x, x)恒为false非对称性asymmetric若lt(x, y)为true则lt(y, x)必为false传递性transitivelt(x, y) lt(y, z)蕴含lt(x, z)等价关系上的传递性若x与y等价!lt(x,y) !lt(y,x)且y与z等价则x与z必然等价。文档中给出了两个经典的反例对Int而言是合法的lt而≤不合法违反非自反性对Float64而言连都非法因为1.0与NaN等价、NaN与2.0等价但1.0与2.0不等价违反第四条。这也解释了为什么默认使用isless——它专门处理了NaN的语义会把NaN排到最后julia sort([2, NaN, 1, NaN, 3]) # 默认 ltisless 的正确排序 5-element Vector{Float64}: 1.0 2.0 3.0 NaN NaN julia sort([2, NaN, 1, NaN, 3], lt) # 非法 lt 导致未定义行为 5-element Vector{Float64}: 2.0 NaN 1.0 NaN 3.0两个元素之间的大小关系定义为revtrue时小于/大于互换x y当且仅当lt(by(x), by(y))为真x与y等价当二者互不小于对方。注意当前实现是每次比较前应用by变换而不是对每个元素只变换一次见 base/sort.jl#L1635-L1639这对有副作用的by函数是有影响的。另外关键字之间存在组合规则lt、by、rev、order各自独立、可自由组合唯一的限制是——当lt不是isless时order只能是Base.Order.Forward或Base.Order.Reverse否则报错见 base/ordering.jl#L135 与 base/sort.jl#L1641-L1647。所有关键字最终都会通过Base.Order.ord(lt, by, rev, order)折叠成一个统一的Ordering对象见下文备选序一节。排序函数全览文档中列出的排序函数包括函数签名要点行为sort!sort!(v; alg, lt, by, rev, order, scratch)原地排序返回v本身sortsort(v; kws...)返回排序后的副本不修改输入sortpermsortperm(A; alg, lt, by, rev, order, scratch, dims...)返回使A[I]有序的排列Isortperm!sortperm!(ix, A; kws...)复用预分配的索引数组ixpartialsort!partialsort!(v, k; kws...)原地把第k个或k区间元素放到全排序后应处的位置partialsortpartialsort(v, k; kws...)partialsort!的复制版本partialsortpermpartialsortperm(v, k; kws...)返回部分排列I使v[I]对应全排序后第k个位置的值partialsortperm!partialsortperm!(ix, v, k; kws...)上述函数的预分配版本sortslicessortslices(A; dims, kws...)按给定维度对多维数组的切片排序sortperm 与 sortperm! 的细节sortperm返回的排列保证稳定即使底层排序算法不稳定即相等元素的索引仍按升序出现见 base/sort.jl#L1919-L1994。对多维数组必须显式传入dims关键字Julia 1.9 起支持。其内部实现有一个有趣的优化路径base/sort.jl#L1981-L1991当输入是整数向量、正向序、且取值范围远小于长度的一半时会走一个专门的sortperm_int_range计数式快速通道base/sort.jl#L2058-L2081。sortperm!要求ix与A具有相同的axes且ix会被初始化为LinearIndices(A)对非向量输入传dims是合法的而对向量传dims会抛出ArgumentError见 base/sort.jl#L2037-L2055。测试 test/sorting.jl#L48-L75 覆盖了包括OffsetVector、dims错误用法在内的各种场景。部分排序partialsort 家族partialsort!并不保证把整个数组排好序只保证位置k上的值等于全排序后该位置的值k也可以是范围此时返回该区间内的值视图。其内部基于BracketedSort实现base/sort.jl#L97-L108该算法通过采样估计分位数夹逼目标区间达到O(n k·log k)的平均复杂度见 base/sort.jl#L1167-L1216 的算法说明。julia a [1, 2, 4, 3, 4]; julia partialsort!(a, 4) 4 julia a 5-element Vector{Int64}: 1 2 3 4 4partialsortperm是partialsort!的排列版本等价于sortperm(...)[k]但更高效且排列是稳定的见 base/sort.jl#L1822-L1854。相关测试见 test/sorting.jl#L121-L141。多维数组与切片排序sort/sort!通过dims关键字支持沿指定维度排序实现于 base/sort.jl#L2085-L2223dims不为 1 时先把目标维度置换到第一位逐块排序后再置换回去sort_chunks!见 base/sort.jl#L2136-L2154。julia A [4 3; 1 2]; julia sort(A, dims 1) 2×2 Matrix{Int64}: 1 2 4 3 julia sort(A, dims 2) 2×2 Matrix{Int64}: 3 4 1 2Base.Sort.sortslices实现在 base/multidimensional.jl#L1840-L1978则对切片整体排序对矩阵dims1表示按行排序、dims2表示按列排序一维切片默认按字典序比较对更高维数组dims可以是元组且元组内的维度顺序决定切片排列的线性次序。julia sortslices([7 3 5; -1 6 4; 9 -2 8], dims1) # 按行排序 3×3 Matrix{Int64}: -1 6 4 7 3 5 9 -2 8 julia sortslices([7 3 5; -1 6 4; 9 -2 8], dims1, lt(x,y)-isless(x[2],y[2])) 3×3 Matrix{Int64}: 9 -2 8 7 3 5 -1 6 4有序数组上的查询issorted 与 searchsorted 家族对已排序的数组Julia 提供了一组基于二分查找的高效查询函数函数返回值语义issorted(itr; lt, by, rev, order)Bool判断集合是否已按指定序排好searchsortedfirst(v, x; kws...)索引第一个不排在x之前的值的索引全部小于x时返回lastindex(v)1searchsortedlast(v, x; kws...)索引最后一个不排在x之后的值的索引全部大于x时返回firstindex(v)-1searchsorted(v, x; kws...)UnitRange与x等价的所有值的索引区间无匹配时返回插入点处的空区间insorted(x, v; kws...)Boolv中是否含有与x等价的元素Julia 1.6 起issorted的底层实现base/sort.jl#L48-L95只是线性扫描判断是否存在后一个小于前一个的相邻对并把关键字折叠成单个Ordering后调用。searchsorted系列对普通向量使用经典二分查找base/sort.jl#L184-L238例如searchsortedfirst在循环中维护半开区间直到长度归零而对算术步长 RangeAbstractRange{:Real}等有基于公式的 O(1) 特化实现base/sort.jl#L241-L302判定条件由FastRangeOrderings约束。注意by函数会同时作用于搜索值x和v中的元素。julia searchsorted([1, 2, 4, 5, 5, 7], 5) # 多个匹配 4:5 julia searchsorted([1, 2, 4, 5, 5, 7], 3) # 无匹配返回插入点处的空区间 3:2 (empty range) julia searchsortedfirst([1, 2, 4, 5, 5, 7], 3) 3 julia searchsortedlast([1, 2, 4, 5, 5, 7], 3) 2 julia insorted(2TWO, [1one, 2two, 4four], byfirst) # 按键比较 trueinsorted的实现只是!isempty(searchsorted(v, x; kw...))见 base/sort.jl#L464-L466。这类函数对 OffsetArray 等非 1 基索引的向量也能正确处理测试见 test/sorting.jl#L602-L628。排序算法公开算法、默认策略与自定义四个公开算法Julia 基础库中公开提供四个排序算法见 doc/src/base/sort.md 的 Sorting Algorithms 一节它们的核心特性可从源码 docstring 中归纳算法稳定性空间策略适用场景InsertionSort稳定原地逐个插入正确位置小规模集合二次复杂度也是各种递归算法的基准情形MergeSort稳定非原地分治合并大规模集合但通常略慢于 QuickSortQuickSort不稳定原地分治分区大规模集合性能好PartialQuickSort(k)不稳定原地分治只需定位v[k]只关心全排序后第k个或k区间元素对应源码InsertionSort InsertionSortAlg()base/sort.jl#L807-L852QuickSort QuickSortAlg()base/sort.jl#L2360-L2374MergeSort MergeSortAlg()base/sort.jl#L2376-L2394PartialQuickSort{T}携带k字段base/sort.jl#L2321-L2358。三个经典算法的实现在文件尾部快排使用三元素取中值选主元selectpivot!base/sort.jl#L2409-L2429和双指针分区partition!base/sort.jl#L2435-L2452并刻意递归较小子问题以保证最坏情况下栈空间为 O(log n)base/sort.jl#L2454-L2470归并排序通过临时向量t0原地归并两半base/sort.jl#L2472-L2514PartialQuickSort则利用j与a.k的位置关系跳过不需要的部分base/sort.jl#L2516-L2540。julia x rand(100); julia k 50:100; julia s1 sort(x; algQuickSort); julia s2 sort(x; algPartialQuickSort(k)); julia map(issorted, (s1, s2)) # PartialQuickSort 不保证整体有序 (true, false) julia map(x-issorted(x[k]), (s1, s2)) # 但目标区间一定有序 (true, true) julia s1[k] s2[k] # 且目标区间的取值与全排序一致 true此外三个经典算法在长度 ≤ 20SMALL_THRESHOLDbase/sort.jl#L1595的子问题上都会回落到SMALL_ALGORITHM即InsertionSortbase/sort.jl#L824-L833以规避递归算法的常数开销。默认算法是实现细节混合策略与稳定保证默认情况下sort家族使用在多数输入上都很快的稳定算法。具体选什么算法属于实现细节允许未来版本调整以提升性能。当前见 doc/src/base/sort.md 与??Base.DEFAULT_STABLE的扩展帮助是一个由RadixSort、ScratchQuickSort、InsertionSort、CountingSort组成的混合体依据输入的类型、大小与组成动态选择。从源码看默认向量算法流水线_DEFAULT_ALGORITHMS_FOR_VECTORSbase/sort.jl#L1580-L1591形如InitialOptimizations( IsUIntMappable( Small{40}(CheckSorted(ComputeExtrema( ConsiderCountingSort(ConsiderRadixSort(Small{80}(ScratchQuickSort())))))), StableCheckSorted( ... )))其执行思路详见DefaultStable的 docstringbase/sort.jl#L1480-L1548可以概括为一条零成本优化优先的流水线InitialOptimizationsbase/sort.jl#L1473-L1478依次尝试SubArrayOptimization解包视图base/sort.jl#L555-L574、MissingOptimization把missing过滤到末尾base/sort.jl#L585-L686、BoolOptimization布尔向量的计数排序特化base/sort.jl#L742-L758、长度 ≤ 10 直接InsertionSort、IEEEFloatOptimization把NaN移到末尾、按符号位分区、其余按无符号整数位比较base/sort.jl#L699-L731。这些 pass 在未触发时几乎零开销IsUIntMappablebase/sort.jl#L774-L780检查能否把元素映射为保持序关系的无符号整数uint_map/uint_unmapbase/sort.jl#L2229-L2289覆盖无符号/有符号整数、Char、浮点数的正向与反向序若能说明序关系是全序不存在比较相等但对象不同可安全使用更激进的优化随后依次是长度 ≤ 40 直接InsertionSortCheckSorted/StableCheckSorted的预排序与逆序检查base/sort.jl#L861-L879、base/sort.jl#L1365-L1379ComputeExtrema计算极值base/sort.jl#L890-L905ConsiderCountingSort在取值范围小于一半长度时使用计数排序base/sort.jl#L918-L933计数排序实现 base/sort.jl#L945-L969ConsiderRadixSort在值域位数足够小时使用稳定的低位优先基数排序base/sort.jl#L978-L1047pass 与chunk_size启发式见 base/sort.jl#L1384-L1441最后回落到长度 80 用InsertionSort、否则用ScratchQuickSortbase/sort.jl#L1050-L1164一个利用 scratch 空间、可保持稳定、平均线性的分治算法。sortperm的默认算法是DEFAULT_UNSTABLEbase/sort.jl#L1563-L1578但如前所述它返回的排列仍保证稳定通过Perm序和稳定化手段实现。defalgbase/sort.jl#L1620-L1624的默认分派是AbstractArray{:Union{Number, Missing}}与Union{}返回DEFAULT_UNSTABLE其余返回DEFAULT_STABLE。!!! compat Julia 1.9Base.Sort.defalg返回的默认排序算法自 Julia 1.9 起保证稳定更早版本在对数值数组排序时存在不稳定的边角情形。为自定义类型定制默认算法你可以通过给Base.Sort.defalg添加特化方法为自定义类型重新配置默认排序算法。文档中的经典例子来自 InlineStrings.jl对包含SmallInlineStrings与Missing的数组使用自定义的InlineStringSortBase.Sort.defalg(::AbstractArray{:Union{SmallInlineStrings, Missing}}) InlineStringSort这是排序算法可扩展性的官方入口alg关键字如sort!(v, algPartialQuickSort(10:20))面向单次调用而defalg面向类型级的默认配置。备选序Ordering 抽象默认情况下sort、searchsorted及相关函数用isless比较元素而Base.Order.Ordering抽象类型提供了一套在同一组元素上定义不同序的机制调用sort!时可通过order关键字传入一个Ordering实例。Ordering 类型体系Ordering抽象类型base/ordering.jl#L21-L29的所有实例通过Base.Order.lt函数定义序关系它是对isless的泛化自定义Ordering上的lt行为同样必须满足严格弱序的全部条件。基础实现base/ordering.jl#L118-L127lt(o::ForwardOrdering, a, b) isless(a,b) lt(o::ReverseOrdering, a, b) lt(o.fwd,b,a) # 反转参数 lt(o::By, a, b) lt(o.order,o.by(a),o.by(b)) lt(o::Lt, a, b) o.lt(a,b) # 直接用用户提供的 lt文档中列出的Ordering相关类型与函数如下名称定义说明Base.Order.Ordering抽象类型base/ordering.jl#L29表示某个集合上的严格弱序Base.Order.lt(o, a, b)函数base/ordering.jl#L118按序o判断a bBase.Order.ord(lt, by, rev, order)函数base/ordering.jl#L155-L160把sort!的关键字折叠成OrderingBase.Order.Forward常量base/ordering.jl#L65按isless的正向序Base.Order.ReverseOrdering(o)包装类型base/ordering.jl#L42反转任意序lt(ReverseOrdering(o), a, b) lt(o, b, a)Base.Order.Reverse常量base/ordering.jl#L72按isless的反向序Base.Order.By(by, order)结构体base/ordering.jl#L80先经by变换再按order比较Base.Order.Lt(lt)结构体base/ordering.jl#L94直接调用用户提供的lt(a, b)Base.Order.Perm(order, data)结构体base/ordering.jl#L105定义在data的索引上的序data[i]小于data[j]时i j相等时按索引数值比较ord的组合逻辑base/ordering.jl#L130-L160值得注意byidentity时直接使用order本身_by(::typeof(identity), order) order零开销ltisless时by被包装进By两者同时非默认时组合为By(by, Lt(lt))最后revtrue时在外面再包一层ReverseOrdering。实际应用示例order关键字与by关键字可以同时使用order中的by变换会在by关键字之后施加见 base/sort.jl#L1644-L1645。sort!文档中的例子julia sort(0:3, byx-x-2, orderBase.Order.By(abs)) 4-element Vector{Int64}: 2 1 3 0 julia sort(0:3, byx-x-2, orderBase.Order.By(abs)) sort(0:3, byx-abs(x-2)) truesortperm的实现正是利用Perm序把对索引排序翻译为按被索引元素比较sort!(ix; orderPerm(ord(lt, by, rev, order), vec(A)))见 base/sort.jl#L1992-L1993 与 base/sort.jl#L2049-L2054。Perm的lt在元素等价时回退到索引数值比较base/ordering.jl#L123-L127这正是sortperm稳定性的来源。测试 test/sorting.jl#L18 起的Order测试集与 test/sorting.jl#L87-L95 的稳定性测试对此做了系统性验证。实战建议与验证优先默认除非有明确理由性能瓶颈定位、稳定性需求、自定义类型否则不要手动指定alg——默认混合策略在类型、大小、组成三个维度上都做了优化且未来会持续改进。需要稳定序时直接用默认Julia 1.9 保证稳定显式选择时InsertionSort小数组与MergeSort大数组是稳定选项。只关心第 k 个元素用partialsort/partialsort!/partialsortperm或algPartialQuickSort(k)可避免完整排序。已排序数组查询用searchsorted*/insorted而非findall/in可享受二分查找或 Range 的 O(1) 公式特化。自定义类型实现isless或自定义lt必须满足严格弱序的四条性质如需专属算法给Base.Sort.defalg加特化方法即可。可参考的测试完整的排序行为契约见 test/sorting.jl其中stabilityL87、Each sorting algorithm individuallyL165、PartialQuickSortL299、advanced sortingL344等测试集覆盖了稳定性、NaN/missing处理、视图与 OffsetArray、整数取值范围优化等关键行为是理解与验证排序语义的首选参考。【免费下载链接】juliaThe Julia Programming Language项目地址: https://gitcode.com/gh_mirrors/ju/julia创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

Julia 排序与排序相关函数完全指南：sort / sortperm / searchsorted 与 Ordering 机制深入解析

相关推荐

Arthas memory 命令详解：查看 JVM 堆、非堆与缓冲区内存信息

你的文献综述，可能一直在“假装学术”

text-to-audio：基于 gTTS 的文本转语音实战指南

更多资讯

Open-Code-Review：开源可审计的AI代码审查范式

大模型工具接入：MCP与Agent方案对比与实践

EffectorP3.0实战：从全蛋白组到候选效应子的高效筛选链路

code-review-graph 完全指南：本地代码知识图谱，让 AI 代码审查只读 1/65 的 token

10分钟跑通Delta Lake湖仓一体：从安装到时间旅行查询的完整指南

AI如何重构保险行业：核保、理赔与定价的智能化实践

今日更新

校园网认证计费模式详解：AAA与代拨架构、原理及排障

Spring Boot+Vue垃圾分类毕设：分层、权限与排错实战

把 Cline 的 Base URL 改到 TaoToken 之后，DeepSeek 仍能修调试配置

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？