排序及相关函数

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

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

You can sort in reverse order as well:

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

sort constructs a sorted copy leaving its input unchanged. Use the "bang" version of the sort function to mutate an existing array:

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

julia> sort!(a);

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

Instead of directly sorting an array, you can compute a permutation of the array's indices that puts the array into sorted order:

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

Arrays can be sorted according to an arbitrary transformation of their values:

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

All the sorting and order related functions rely on a "less than" relation defining a strict weak order on the values to be manipulated. The isless function is invoked by default, but the relation can be specified via the lt keyword, a function that takes two array elements and returns true if and only if the first argument is "less than" the second. See sort! and Alternate Orderings for more information.

排序函数

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

排序及相关函数

排序函数

排列顺序相关的函数

排序算法

Alternate Orderings