排序及相关函数

Julia 拥有广泛而灵活的应用程序接口，可用于对已排序的数组值进行排序和交互。默认情况下，Julia 会选择合理的算法并按升序排序：

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

或者指定使用逆序：

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

sort 构造一个已排序的副本，保持输入不变。使用排序函数的"感叹号"版本来修改现有数组：

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

julia> sort!(a);

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

除了直接对数组进行排序，你还可以计算一个数组索引的置换，使数组按排序顺序排列：

julia> v = randn(5)
5-element Array{Float64,1}:
  0.297288
  0.382396
 -0.597634
 -0.0104452
 -0.839027

julia> p = sortperm(v)
5-element Array{Int64,1}:
 5
 3
 4
 1
 2

julia> v[p]
5-element Array{Float64,1}:
 -0.839027
 -0.597634
 -0.0104452
  0.297288
  0.382396

数组可以根据其值的任意转换进行排序：

julia> sort(v, by=abs)
5-element Array{Float64,1}:
 -0.0104452
  0.297288
  0.382396
 -0.597634
 -0.839027

或者指定使用逆序：

julia> sort(v, by=abs, rev=true)
5-element Array{Float64,1}:
 -0.839027
 -0.597634
  0.382396
  0.297288
 -0.0104452

如有必要，可以选择排序算法：

julia> sort(v, alg=InsertionSort)
5-element Array{Float64,1}:
 -0.839027
 -0.597634
 -0.0104452
  0.297288
  0.382396

所有排序和顺序相关的函数都依赖于一个"小于"关系，该关系在要操作的值上定义了一个严格弱序。默认调用 isless 函数，但可以通过 lt 关键字指定关系，这是一个接受两个数组元素的函数，当且仅当第一个参数"小于"第二个参数时返回 true。更多信息请参见 sort! 和替代排序。

排序函数

Base.sort! — Function

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

Sort the vector v in place. A stable algorithm is used by default: the ordering of elements that compare equal is preserved. A specific algorithm can be selected via the alg keyword (see Sorting Algorithms for available algorithms).

Elements are first transformed with the function by and then compared according to either the function lt or the ordering order. Finally, the resulting order is reversed if rev=true (this preserves forward stability: elements that compare equal are not reversed). The current implemention applies the by transformation before each comparison rather than once per element.

Passing an lt other than isless along with an order other than Base.Order.Forward or Base.Order.Reverse is not permitted, otherwise all options are independent and can be used together in all possible combinations. Note that order can also include a "by" transformation, in which case it is applied after that defined with the by keyword. For more information on order values see the documentation on Alternate Orderings.

Relations between two elements are defined as follows (with "less" and "greater" exchanged when rev=true):

x is less than y if lt(by(x), by(y)) (or Base.Order.lt(order, by(x), by(y))) yields true.
x is greater than y if y is less than x.
x and y are equivalent if neither is less than the other ("incomparable" is sometimes used as a synonym for "equivalent").

The result of sort! is sorted in the sense that every element is greater than or equivalent to the previous one.

The lt function must define a strict weak order, that is, it must be

irreflexive: lt(x, x) always yields false,
asymmetric: if lt(x, y) yields true then lt(y, x) yields false,
transitive: lt(x, y) && lt(y, z) implies lt(x, z),
transitive in equivalence: !lt(x, y) && !lt(y, x) and !lt(y, z) && !lt(z, y) together imply !lt(x, z) && !lt(z, x). In words: if x and y are equivalent and y and z are equivalent then x and z must be equivalent.

For example < is a valid lt function for Int values but ≤ is not: it violates irreflexivity. For Float64 values even < is invalid as it violates the fourth condition: 1.0 and NaN are equivalent and so are NaN and 2.0 but 1.0 and 2.0 are not equivalent.

Examples

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

排序及相关函数

排序函数

排列顺序相关的函数

排序算法

替代排序