排序和相关函数

sort!(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

就地排序向量 v。默认情况下使用稳定算法：比较相等的元素的顺序将保留。可以通过 alg 关键字选择特定算法（有关可用算法，请参阅 排序算法）。

元素首先使用函数 by 进行转换，然后根据函数 lt 或排序 order 进行比较。最后，如果 rev=true，则将结果顺序反转（这将保留正向稳定性：比较相等的元素不会反转）。当前实现将在每次比较之前应用 by 转换，而不是对每个元素应用一次。

除了 isless 之外，传递 lt 与除了 Base.Order.Forward 或 Base.Order.Reverse 之外的 order 是不允许的，否则所有选项都是独立的，可以以所有可能的组合一起使用。请注意，order 也可以包含“by”转换，在这种情况下，它将在使用 by 关键字定义的转换之后应用。有关 order 值的更多信息，请参阅有关 备用排序 的文档。

两个元素之间的关系定义如下（当 rev=true 时，“小于”和“大于”交换）

• 如果 lt(by(x), by(y))（或 Base.Order.lt(order, by(x), by(y))）为真，则 x 小于 y。
• 如果 y 小于 x，则 x 大于 y。
• 如果两者都不小于对方，则 x 和 y 等效（“不可比较”有时用作“等效”的同义词）。

sort! 的结果在以下意义上是已排序的：每个元素都大于或等于前一个元素。

lt 函数必须定义一个严格的弱顺序，即它必须是

• 非自反的：lt(x, x) 始终为 false，
• 非对称的：如果 lt(x, y) 为 true，则 lt(y, x) 为 false，
• 传递的：lt(x, y) && lt(y, z) 意味着 lt(x, z)，
• 等效性传递的：!lt(x, y) && !lt(y, x) 和 !lt(y, z) && !lt(z, y) 共同意味着 !lt(x, z) && !lt(z, x)。换句话说：如果 x 和 y 等效，y 和 z 等效，则 x 和 z 必须等效。

例如，< 是 Int 值的有效 lt 函数，但 ≤ 不是：它违反了非自反性。对于 Float64 值，即使 < 也是无效的，因为它违反了第四个条件：1.0 和 NaN 等效，NaN 和 2.0 等效，但 1.0 和 2.0 不等效。

另请参阅 sort、sortperm、sortslices、partialsort!、partialsortperm、issorted、searchsorted、insorted、Base.Order.ord。

示例

julia> v = [3, 1, 2]; sort!(v); v
3-element Vector{Int64}:
 1
 2
 3

julia> v = [3, 1, 2]; sort!(v, rev = true); v
3-element Vector{Int64}:
 3
 2
 1

julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[1]); v
3-element Vector{Tuple{Int64, String}}:
 (1, "c")
 (2, "b")
 (3, "a")

julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[2]); v
3-element Vector{Tuple{Int64, String}}:
 (3, "a")
 (2, "b")
 (1, "c")

julia> sort(0:3, by=x->x-2, order=Base.Order.By(abs)) # same as sort(0:3, by=abs(x->x-2))
4-element Vector{Int64}:
 2
 1
 3
 0

julia> sort([2, NaN, 1, NaN, 3]) # correct sort with default lt=isless
5-element Vector{Float64}:
   1.0
   2.0
   3.0
 NaN
 NaN

julia> sort([2, NaN, 1, NaN, 3], lt=<) # wrong sort due to invalid lt. This behavior is undefined.
5-element Vector{Float64}:
   2.0
 NaN
   1.0
 NaN
   3.0

sort!(A; dims::Integer, alg::Algorithm=defalg(A), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

沿维度 dims 排序多维数组 A。有关可能的关键字参数的说明，请参阅 sort! 的一维版本。

要排序数组的切片，请参阅 sortslices。

示例

julia> A = [4 3; 1 2]
2×2 Matrix{Int64}:
 4  3
 1  2

julia> sort!(A, dims = 1); A
2×2 Matrix{Int64}:
 1  2
 4  3

julia> sort!(A, dims = 2); A
2×2 Matrix{Int64}:
 1  2
 3  4

sort(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

sort! 的变体，它返回 v 的已排序副本，并将 v 本身保持不变。

示例

julia> v = [3, 1, 2];

julia> sort(v)
3-element Vector{Int64}:
 1
 2
 3

julia> v
3-element Vector{Int64}:
 3
 1
 2

sort(A; dims::Integer, alg::Algorithm=defalg(A), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

沿给定维度排序多维数组 A。有关可能的关键字参数的说明，请参阅 sort!。

要排序数组的切片，请参阅 sortslices。

示例

julia> A = [4 3; 1 2]
2×2 Matrix{Int64}:
 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  2

sortperm(A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, [dims::Integer])

返回一个排列向量或数组 I，该向量或数组将 A[I] 沿给定维度置于已排序的顺序。如果 A 具有多个维度，则必须指定 dims 关键字参数。顺序使用与 sort! 相同的关键字指定。即使排序算法不稳定，排列也保证稳定：相等元素的索引将按升序排列。

另请参阅 sortperm!、partialsortperm、invperm、indexin。要排序数组的切片，请参阅 sortslices。

示例

julia> v = [3, 1, 2];

julia> p = sortperm(v)
3-element Vector{Int64}:
 2
 3
 1

julia> v[p]
3-element Vector{Int64}:
 1
 2
 3

julia> A = [8 7; 5 6]
2×2 Matrix{Int64}:
 8  7
 5  6

julia> sortperm(A, dims = 1)
2×2 Matrix{Int64}:
 2  4
 1  3

julia> sortperm(A, dims = 2)
2×2 Matrix{Int64}:
 3  1
 2  4

InsertionSort

使用插入排序算法。

插入排序一次遍历一个元素，将每个元素插入到输出向量中正确的已排序位置。

特点

• 稳定：保留比较相等的元素的顺序

（例如，在忽略大小写的字母排序中，“a”和“A”）。

• 在内存中就地进行。
• 在要排序的元素数量方面具有二次性能

它非常适合小型集合，但不要用于大型集合。

MergeSort

指示排序函数应使用归并排序算法。归并排序将集合划分为子集合，并反复将它们合并，在每一步都对每个子集合进行排序，直到整个集合以已排序的形式重新组合。

特点

• 稳定：保留比较相等的元素的顺序（例如，在忽略大小写的字母排序中，“a”和“A”）。
• 在内存中非就地进行。
• 分治排序策略。
• 对于大型集合，性能良好，但通常不如QuickSort快。

QuickSort

指示排序函数应该使用快速排序算法，该算法不稳定。

特点

• 不稳定：不保留比较相等元素的排序顺序（例如，在忽略大小写字母排序中，"a" 和 "A"）。
• 在内存中就地进行。
• 分治：类似于MergeSort的排序策略。
• 对于大型集合，性能良好。

PartialQuickSort{T <: Union{Integer,OrdinalRange}}

指示排序函数应该使用部分快速排序算法。PartialQuickSort(k) 类似于 QuickSort，但只需要找到并排序最终会出现在 v[k] 中的元素，假设 v 已完全排序。

特点

• 不稳定：不保留比较相等元素的排序顺序（例如，在忽略大小写字母排序中，"a" 和 "A"）。
• 在内存中就地进行。
• 分治：类似于MergeSort的排序策略。

请注意，PartialQuickSort(k) 不一定对整个数组进行排序。例如，

julia> x = rand(100);

julia> k = 50:100;

julia> s1 = sort(x; alg=QuickSort);

julia> s2 = sort(x; alg=PartialQuickSort(k));

julia> map(issorted, (s1, s2))
(true, false)

julia> map(x->issorted(x[k]), (s1, s2))
(true, true)

julia> s1[k] == s2[k]
true

sortperm!(ix, A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, [dims::Integer])

类似于sortperm，但接受预分配的索引向量或数组 ix，其 axes 与 A 相同。ix 被初始化为包含值 LinearIndices(A)。

示例

julia> v = [3, 1, 2]; p = zeros(Int, 3);

julia> sortperm!(p, v); p
3-element Vector{Int64}:
 2
 3
 1

julia> v[p]
3-element Vector{Int64}:
 1
 2
 3

julia> A = [8 7; 5 6]; p = zeros(Int,2, 2);

julia> sortperm!(p, A; dims=1); p
2×2 Matrix{Int64}:
 2  4
 1  3

julia> sortperm!(p, A; dims=2); p
2×2 Matrix{Int64}:
 3  1
 2  4

sortslices(A; dims, alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

对数组 A 的切片进行排序。必需的关键字参数 dims 必须是整数或整数元组。它指定切片排序的维度。

例如，如果 A 是一个矩阵，dims=1 将对行进行排序，dims=2 将对列进行排序。请注意，一维切片上的默认比较函数按字典序排序。

对于其余关键字参数，请参见sort! 文档。

示例

julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1) # Sort rows
3×3 Matrix{Int64}:
 -1   6  4
  7   3  5
  9  -2  8

julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1, lt=(x,y)->isless(x[2],y[2]))
3×3 Matrix{Int64}:
  9  -2  8
  7   3  5
 -1   6  4

julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1, rev=true)
3×3 Matrix{Int64}:
  9  -2  8
  7   3  5
 -1   6  4

julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2) # Sort columns
3×3 Matrix{Int64}:
  3   5  7
 -1  -4  6
 -2   8  9

julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2, alg=InsertionSort, lt=(x,y)->isless(x[2],y[2]))
3×3 Matrix{Int64}:
  5   3  7
 -4  -1  6
  8  -2  9

julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2, rev=true)
3×3 Matrix{Int64}:
 7   5   3
 6  -4  -1
 9   8  -2

更高维度

sortslices 自然地扩展到更高维度。例如，如果 A 是一个 2x2x2 数组，sortslices(A, dims=3) 将对第 3 维内的切片进行排序，将 2x2 切片 A[:, :, 1] 和 A[:, :, 2] 传递给比较函数。请注意，虽然更高维切片没有默认顺序，但可以使用 by 或 lt 关键字参数指定此类顺序。

如果 dims 是一个元组，则 dims 中维度的顺序是相关的，并指定切片的线性顺序。例如，如果 A 是三维的，而 dims 是 (1, 2)，则前两个维度的排序将重新排列，使得切片（剩余的第三维）按顺序排序。如果 dims 是 (2, 1)，则将取相同的切片，但结果顺序将是行优先的。

更高维度示例

julia> A = permutedims(reshape([4 3; 2 1; 'A' 'B'; 'C' 'D'], (2, 2, 2)), (1, 3, 2))
2×2×2 Array{Any, 3}:
[:, :, 1] =
 4  3
 2  1

[:, :, 2] =
 'A'  'B'
 'C'  'D'

julia> sortslices(A, dims=(1,2))
2×2×2 Array{Any, 3}:
[:, :, 1] =
 1  3
 2  4

[:, :, 2] =
 'D'  'B'
 'C'  'A'

julia> sortslices(A, dims=(2,1))
2×2×2 Array{Any, 3}:
[:, :, 1] =
 1  2
 3  4

[:, :, 2] =
 'D'  'C'
 'B'  'A'

julia> sortslices(reshape([5; 4; 3; 2; 1], (1,1,5)), dims=3, by=x->x[1,1])
1×1×5 Array{Int64, 3}:
[:, :, 1] =
 1

[:, :, 2] =
 2

[:, :, 3] =
 3

[:, :, 4] =
 4

[:, :, 5] =
 5

issorted(v, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

测试集合是否按排序顺序。关键字修改了被认为排序的顺序，如sort! 文档中所述。

示例

julia> issorted([1, 2, 3])
true

julia> issorted([(1, "b"), (2, "a")], by = x -> x[1])
true

julia> issorted([(1, "b"), (2, "a")], by = x -> x[2])
false

julia> issorted([(1, "b"), (2, "a")], by = x -> x[2], rev=true)
true

julia> issorted([1, 2, -2, 3], by=abs)
true

searchsorted(v, x; by=identity, lt=isless, rev=false)

返回 v 中值与 x 相等的索引范围，或者如果 v 不包含与 x 相等的元素，则返回位于插入点的空范围。向量 v 必须根据关键字定义的顺序进行排序。有关关键字的含义和等效性的定义，请参考sort!。请注意，by 函数将应用于搜索值 x 以及 v 中的值。

范围通常使用二分查找找到，但对于某些输入，有优化的实现。

另请参见：searchsortedfirst、sort!、insorted、findall。

示例

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

julia> searchsorted([1=>"one", 2=>"two", 2=>"two", 4=>"four"], 2=>"two", by=first) # compare the keys of the pairs
2:3

searchsortedfirst(v, x; by=identity, lt=isless, rev=false)

返回 v 中第一个大于或等于 x 的值的索引。如果 x 大于 v 中的所有值，则返回 lastindex(v) + 1。

向量 v 必须根据关键字定义的顺序进行排序。在返回的索引处插入 x 将保持排序顺序。有关关键字的含义以及“大于”和等效性的定义，请参考sort!。请注意，by 函数将应用于搜索值 x 以及 v 中的值。

索引通常使用二分查找找到，但对于某些输入，有优化的实现。

另请参见：searchsortedlast、searchsorted、findfirst。

示例

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 4) # single match
3

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 5) # multiple matches
4

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1

julia> searchsortedfirst([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # compare the keys of the pairs
3

searchsortedlast(v, x; by=identity, lt=isless, rev=false)

返回 v 中最后一个小于或等于 x 的值的索引。如果 x 小于 v 中的所有值，则该函数返回 firstindex(v) - 1。

向量 v 必须根据关键字定义的顺序进行排序。有关关键字的含义以及“小于”和等效性的定义，请参考sort!。请注意，by 函数将应用于搜索值 x 以及 v 中的值。

索引通常使用二分查找找到，但对于某些输入，有优化的实现。

示例

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 4) # single match
3

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 5) # multiple matches
5

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
2

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
6

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
0

julia> searchsortedlast([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # compare the keys of the pairs
2

insorted(x, v; by=identity, lt=isless, rev=false) -> Bool

确定向量 v 是否包含任何与 x 相等的元素。向量 v 必须根据关键字定义的顺序进行排序。有关关键字的含义和等效性的定义，请参考sort!。请注意，by 函数将应用于搜索值 x 以及 v 中的值。

检查通常使用二分查找完成，但对于某些输入，有优化的实现。

另请参见in。

示例

julia> insorted(4, [1, 2, 4, 5, 5, 7]) # single match
true

julia> insorted(5, [1, 2, 4, 5, 5, 7]) # multiple matches
true

julia> insorted(3, [1, 2, 4, 5, 5, 7]) # no match
false

julia> insorted(9, [1, 2, 4, 5, 5, 7]) # no match
false

julia> insorted(0, [1, 2, 4, 5, 5, 7]) # no match
false

julia> insorted(2=>"TWO", [1=>"one", 2=>"two", 4=>"four"], by=first) # compare the keys of the pairs
true

partialsort!(v, k; by=identity, lt=isless, rev=false)

就地部分排序向量 v，使得索引 k 处的值（如果 k 是一个范围，则为相邻值的范围）出现在如果数组完全排序时它将出现的位置。如果 k 是一个单一索引，则返回该值；如果 k 是一个范围，则返回这些索引处值的数组。请注意，partialsort! 可能不会完全排序输入数组。

有关关键字参数，请参见sort! 文档。

示例

julia> a = [1, 2, 4, 3, 4]
5-element Vector{Int64}:
 1
 2
 4
 3
 4

julia> partialsort!(a, 4)
4

julia> a
5-element Vector{Int64}:
 1
 2
 3
 4
 4

julia> a = [1, 2, 4, 3, 4]
5-element Vector{Int64}:
 1
 2
 4
 3
 4

julia> partialsort!(a, 4, rev=true)
2

julia> a
5-element Vector{Int64}:
 4
 4
 3
 2
 1

partialsort(v, k, by=identity, lt=isless, rev=false)

对partialsort! 的变体，它在部分排序之前复制 v，从而返回与 partialsort! 相同的结果，但保持 v 不变。

partialsortperm(v, k; by=ientity, lt=isless, rev=false)

返回向量 v 的部分排列 I，使得 v[I] 返回完全排序的 v 版本在索引 k 处的值。如果 k 是一个范围，则返回一个索引向量；如果 k 是一个整数，则返回一个单一索引。顺序使用与 sort! 相同的关键字指定。排列是稳定的：相等元素的索引将按升序出现。

此函数等效于，但比调用 sortperm(...)[k] 更有效。

示例

julia> v = [3, 1, 2, 1];

julia> v[partialsortperm(v, 1)]
1

julia> p = partialsortperm(v, 1:3)
3-element view(::Vector{Int64}, 1:3) with eltype Int64:
 2
 4
 3

julia> v[p]
3-element Vector{Int64}:
 1
 1
 2

partialsortperm!(ix, v, k; by=identity, lt=isless, rev=false)

类似于partialsortperm，但接受预分配的索引向量 ix，大小与 v 相同，用于存储（v 索引的排列）。

ix 被初始化为包含 v 的索引。

（通常，v 的索引将是 1:length(v)，但是如果 v 具有使用非基于一的索引的替代数组类型，例如 OffsetArray，则 ix 必须共享相同的索引）

在返回时，保证 ix 具有在排序位置的索引 k，使得

partialsortperm!(ix, v, k);
v[ix[k]] == partialsort(v, k)

如果 k 是一个整数，则返回值是 ix 的第 k 个元素；如果 k 是一个范围，则返回值是 ix 中的视图。

示例

julia> v = [3, 1, 2, 1];

julia> ix = Vector{Int}(undef, 4);

julia> partialsortperm!(ix, v, 1)
2

julia> ix = [1:4;];

julia> partialsortperm!(ix, v, 2:3)
2-element view(::Vector{Int64}, 2:3) with eltype Int64:
 4
 3

Base.Order.Ordering

表示某些元素集合上的全序的抽象类型。

使用 Base.Order.lt 根据排序比较两个元素。

lt(o::Ordering, a, b)

测试 a 是否小于 b，根据排序 o。

ord(lt, by, rev::Union{Bool, Nothing}, order::Ordering=Forward)

从 sort! 使用的相同参数构造一个 Ordering 对象。元素首先通过函数 by（可能是 identity）进行转换，然后根据函数 lt 或现有排序 order 进行比较。lt 应为 isless 或一个遵守与 sort! 的 lt 参数相同的规则的函数。最后，如果 rev=true，则反转结果顺序。

传递 lt（除了 isless）以及 order（除了 Base.Order.Forward 或 Base.Order.Reverse）是不允许的，否则所有选项都是独立的，可以以所有可能的组合一起使用。

Base.Order.Forward

根据 isless 的默认排序。

ReverseOrdering(fwd::Ordering=Forward)

一个反转排序的包装器。

对于给定的 Ordering o，以下对于所有 a、b 成立

lt(ReverseOrdering(o), a, b) == lt(o, b, a)

Base.Order.Reverse

根据 isless 的反转排序。

By(by, order::Ordering=Forward)

Ordering，它在元素经过函数 by 转换后应用 order。

Lt(lt)

Ordering，它调用 lt(a, b) 来比较元素。lt 必须遵守与 sort! 的 lt 参数相同的规则。

Perm(order::Ordering, data::AbstractVector)

data 的索引上的 Ordering，其中 i 小于 j，如果 data[i] 小于 data[j]，根据 order。在 data[i] 和 data[j] 相等的情况下，i 和 j 通过数值进行比较。