排序及相关函数

    你同样可以轻松实现逆序排序：

    2. 3-element Vector{Int64}:
    3.  3
    4.  2
    5.  1

    对数组进行 in-place 排序时，要使用 ! 版的排序函数：

    1. julia> a = [2,3,1];
    3. julia> sort!(a);
    5. julia> a
    6. 3-element Vector{Int64}:
    7.  1
    8.  2
    9.  3

    你可以计算用于排列的索引，而不是直接对数组进行排序：

    1. julia> v = randn(5)
    2. 5-element Array{Float64,1}:
    3.   0.297288
    4.   0.382396
    5.  -0.597634
    6.  -0.0104452
    7.  -0.839027
    9. julia> p = sortperm(v)
    10. 5-element Array{Int64,1}:
    11.  5
    12.  3
    13.  4
    14.  1
    15.  2
    17. julia> v[p]
    18. 5-element Array{Float64,1}:
    19.  -0.839027
    20.  -0.597634
    21.  -0.0104452
    22.   0.297288
    23.   0.382396

    数组可以根据对其值任意的转换结果来进行排序；

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

    或者通过转换来进行逆序排序

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

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

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

    所有与排序和顺序相关的函数依赖于“小于”关系，该关系定义了要操纵的值的总顺序。默认情况下会调用 isless 函数，但可以通过 lt 关键字指定关系。

    — Function

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

    Sort the vector v in place. QuickSort is used by default for numeric arrays while is used for other arrays. You can specify an algorithm to use via the alg keyword (see Sorting Algorithms for available algorithms). The by keyword lets you provide a function that will be applied to each element before comparison; the lt keyword allows providing a custom “less than” function (note that for every x and y, only one of lt(x,y) and lt(y,x) can return true); use rev=true to reverse the sorting order. These options are independent and can be used together in all possible combinations: if both by and lt are specified, the lt function is applied to the result of the by function; rev=true reverses whatever ordering specified via the by and lt keywords.

    Examples

    1. julia> v = [3, 1, 2]; sort!(v); v
    2. 3-element Vector{Int64}:
    3.  1
    4.  2
    5.  3
    7. julia> v = [3, 1, 2]; sort!(v, rev = true); v
    8. 3-element Vector{Int64}:
    9.  3
    10.  2
    11.  1
    13. julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[1]); v
    14. 3-element Vector{Tuple{Int64, String}}:
    15.  (1, "c")
    16.  (2, "b")
    17.  (3, "a")
    19. julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[2]); v
    20. 3-element Vector{Tuple{Int64, String}}:
    21.  (3, "a")
    22.  (2, "b")
    23.  (1, "c")

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

    Sort the multidimensional array A along dimension dims. See sort! for a description of possible keyword arguments.

    To sort slices of an array, refer to .

    Julia 1.1

    This function requires at least Julia 1.1.

    Examples

    1. julia> A = [4 3; 1 2]
    2. 2×2 Matrix{Int64}:
    3.  4  3
    4.  1  2
    6. julia> sort!(A, dims = 1); A
    7. 2×2 Matrix{Int64}:
    8.  1  2
    9.  4  3
    11. julia> sort!(A, dims = 2); A
    12. 2×2 Matrix{Int64}:
    13.  1  2
    14.  3  4

    source

    — Function

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

    Variant of sort! that returns a sorted copy of v leaving v itself unmodified.

    Examples

    1. julia> v = [3, 1, 2];
    3. julia> sort(v)
    4. 3-element Vector{Int64}:
    5.  1
    6.  2
    7.  3
    9. julia> v
    10. 3-element Vector{Int64}:
    11.  3
    12.  1
    13.  2

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

    Sort a multidimensional array A along the given dimension. See sort! for a description of possible keyword arguments.

    To sort slices of an array, refer to .

    Examples

    1. julia> A = [4 3; 1 2]
    2. 2×2 Matrix{Int64}:
    3.  4  3
    4.  1  2
    6. julia> sort(A, dims = 1)
    7. 2×2 Matrix{Int64}:
    8.  1  2
    9.  4  3
    11. julia> sort(A, dims = 2)
    12. 2×2 Matrix{Int64}:
    13.  3  4
    14.  1  2

    source

    — Function

    1. sortperm(v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

    Return a permutation vector I that puts v[I] in sorted order. The order is specified using the same keywords as sort!. The permutation is guaranteed to be stable even if the sorting algorithm is unstable, meaning that indices of equal elements appear in ascending order.

    See also , partialsortperm, , indexin.

    Examples

    1. julia> v = [3, 1, 2];
    3. julia> p = sortperm(v)
    4. 3-element Vector{Int64}:
    5.  2
    6.  3
    7.  1
    9. julia> v[p]
    10. 3-element Vector{Int64}:
    11.  2
    12.  3

    Base.Sort.InsertionSort — Constant

    1. InsertionSort

    Indicate that a sorting function should use the insertion sort algorithm. Insertion sort traverses the collection one element at a time, inserting each element into its correct, sorted position in the output list.

    Characteristics:

    • stable: preserves the ordering of elements which compare equal (e.g. “a” and “A” in a sort of letters which ignores case).
    • in-place in memory.
    • quadratic performance in the number of elements to be sorted: it is well-suited to small collections but should not be used for large ones.

    Base.Sort.MergeSort — Constant

    Indicate that a sorting function should use the merge sort algorithm. Merge sort divides the collection into subcollections and repeatedly merges them, sorting each subcollection at each step, until the entire collection has been recombined in sorted form.

    Characteristics:

    • stable: preserves the ordering of elements which compare equal (e.g. “a” and “A” in a sort of letters which ignores case).
    • not in-place in memory.
    • divide-and-conquer sort strategy.

    Base.Sort.QuickSort — Constant

    1. QuickSort

    Indicate that a sorting function should use the quick sort algorithm, which is not stable.

    Characteristics:

    • not stable: does not preserve the ordering of elements which compare equal (e.g. “a” and “A” in a sort of letters which ignores case).
    • in-place in memory.
    • divide-and-conquer: sort strategy similar to .
    • good performance for large collections.

    source

    — Type

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

    Indicate that a sorting function should use the partial quick sort algorithm. Partial quick sort returns the smallest k elements sorted from smallest to largest, finding them and sorting them using QuickSort.

    Characteristics:

    • not stable: does not preserve the ordering of elements which compare equal (e.g. “a” and “A” in a sort of letters which ignores case).
    • in-place in memory.
    • divide-and-conquer: sort strategy similar to .

    source

    — Function

    1. sortperm!(ix, v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, initialized::Bool=false)

    Like sortperm, but accepts a preallocated index vector ix. If initialized is false (the default), ix is initialized to contain the values 1:length(v).

    1. julia> v = [3, 1, 2]; p = zeros(Int, 3);
    3. julia> sortperm!(p, v); p
    4. 3-element Vector{Int64}:
    5.  2
    6.  3
    7.  1
    9. julia> v[p]
    10. 3-element Vector{Int64}:
    11.  1
    12.  2
    13.  3

    Base.sortslices — Function

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

    Sort slices of an array A. The required keyword argument dims must be either an integer or a tuple of integers. It specifies the dimension(s) over which the slices are sorted.

    E.g., if A is a matrix, dims=1 will sort rows, dims=2 will sort columns. Note that the default comparison function on one dimensional slices sorts lexicographically.

    For the remaining keyword arguments, see the documentation of .

    Examples

    1. julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1) # Sort rows
    2. 3×3 Matrix{Int64}:
    3.  -1   6  4
    4.   7   3  5
    5.   9  -2  8
    7. julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1, lt=(x,y)->isless(x[2],y[2]))
    8. 3×3 Matrix{Int64}:
    9.   9  -2  8
    10.   7   3  5
    11.  -1   6  4
    13. julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1, rev=true)
    14. 3×3 Matrix{Int64}:
    15.   9  -2  8
    16.   7   3  5
    17.  -1   6  4
    19. julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2) # Sort columns
    20. 3×3 Matrix{Int64}:
    21.   3   5  7
    22.  -1  -4  6
    23.  -2   8  9
    25. julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2, alg=InsertionSort, lt=(x,y)->isless(x[2],y[2]))
    26. 3×3 Matrix{Int64}:
    27.   5   3  7
    28.  -4  -1  6
    29.   8  -2  9
    31. julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2, rev=true)
    32. 3×3 Matrix{Int64}:
    33.  7   5   3
    34.  6  -4  -1
    35.  9   8  -2

    Higher dimensions

    sortslices extends naturally to higher dimensions. E.g., if A is a a 2x2x2 array, sortslices(A, dims=3) will sort slices within the 3rd dimension, passing the 2x2 slices A[:, :, 1] and A[:, :, 2] to the comparison function. Note that while there is no default order on higher-dimensional slices, you may use the by or lt keyword argument to specify such an order.

    If dims is a tuple, the order of the dimensions in dims is relevant and specifies the linear order of the slices. E.g., if A is three dimensional and dims is (1, 2), the orderings of the first two dimensions are re-arranged such that the slices (of the remaining third dimension) are sorted. If dims is (2, 1) instead, the same slices will be taken, but the result order will be row-major instead.

    Higher dimensional examples

    1. julia> A = permutedims(reshape([4 3; 2 1; 'A' 'B'; 'C' 'D'], (2, 2, 2)), (1, 3, 2))
    2. 2×2×2 Array{Any, 3}:
    3. [:, :, 1] =
    4.  4  3
    5.  2  1
    7. [:, :, 2] =
    8.  'A'  'B'
    9.  'C'  'D'
    11. julia> sortslices(A, dims=(1,2))
    12. 2×2×2 Array{Any, 3}:
    13. [:, :, 1] =
    14.  1  3
    15.  2  4
    17. [:, :, 2] =
    18.  'D'  'B'
    19.  'C'  'A'
    21. julia> sortslices(A, dims=(2,1))
    22. 2×2×2 Array{Any, 3}:
    23. [:, :, 1] =
    24.  1  2
    25.  3  4
    27. [:, :, 2] =
    28.  'D'  'C'
    29.  'B'  'A'
    31. julia> sortslices(reshape([5; 4; 3; 2; 1], (1,1,5)), dims=3, by=x->x[1,1])
    32. 1×1×5 Array{Int64, 3}:
    33. [:, :, 1] =
    34.  1
    36. [:, :, 2] =
    37.  2
    39. [:, :, 3] =
    40.  3
    42. [:, :, 4] =
    43.  4
    45. [:, :, 5] =
    46.  5

    source

    — Function

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

    Test whether a vector is in sorted order. The lt, by and rev keywords modify what order is considered to be sorted just as they do for sort.

    Examples

    1. julia> issorted([1, 2, 3])
    2. true
    4. julia> issorted([(1, "b"), (2, "a")], by = x -> x[1])
    5. true
    7. julia> issorted([(1, "b"), (2, "a")], by = x -> x[2])
    8. false
    10. julia> issorted([(1, "b"), (2, "a")], by = x -> x[2], rev=true)
    11. true

    Base.Sort.searchsorted — Function

    1. searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

    Return the range of indices of a which compare as equal to x (using binary search) according to the order specified by the by, lt and rev keywords, assuming that a is already sorted in that order. Return an empty range located at the insertion point if a does not contain values equal to x.

    See also: , searchsortedfirst, , findall.

    Examples

    1. julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
    2. 3:3
    4. julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
    5. 4:5
    7. julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
    8. 3:2
    10. julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
    11. 7:6
    13. julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
    14. 1:0

    Base.Sort.searchsortedfirst — Function

      Return the index of the first value in a greater than or equal to x, according to the specified order. Return length(a) + 1 if x is greater than all values in a. a is assumed to be sorted.

      See also: , searchsorted, .

      Examples

      1. julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 4) # single match
      2. 3
      4. julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 5) # multiple matches
      5. 4
      7. julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
      8. 3
      10. julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
      11. 7
      13. julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
      14. 1

      source

      — Function

      1. searchsortedlast(a, x; by=<transform>, lt=<comparison>, rev=false)

      Return the index of the last value in a less than or equal to x, according to the specified order. Return 0 if x is less than all values in a. a is assumed to be sorted.

      Examples

      1. julia> searchsortedlast([1, 2, 4, 5, 5, 7], 4) # single match
      2. 3
      4. julia> searchsortedlast([1, 2, 4, 5, 5, 7], 5) # multiple matches
      5. 5
      7. julia> searchsortedlast([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
      8. 2
      10. julia> searchsortedlast([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
      11. 6
      13. julia> searchsortedlast([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
      14. 0

      source

      — Function

      1. insorted(a, x; by=<transform>, lt=<comparison>, rev=false) -> Bool

      Determine whether an item is in the given sorted collection, in the sense that it is \== to one of the values of the collection according to the order specified by the by, lt and rev keywords, assuming that a is already sorted in that order, see for the keywords.

      See also in.

      Examples

      1. julia> insorted(4, [1, 2, 4, 5, 5, 7]) # single match
      2. true
      4. julia> insorted(5, [1, 2, 4, 5, 5, 7]) # multiple matches
      5. true
      7. julia> insorted(3, [1, 2, 4, 5, 5, 7]) # no match
      8. false
      10. julia> insorted(9, [1, 2, 4, 5, 5, 7]) # no match
      11. false
      13. julia> insorted(0, [1, 2, 4, 5, 5, 7]) # no match
      14. false

      Julia 1.6

      insorted was added in Julia 1.6.

      Base.Sort.partialsort! — Function

      Partially sort the vector v in place, according to the order specified by by, lt and rev so that the value at index k (or range of adjacent values if k is a range) occurs at the position where it would appear if the array were fully sorted via a non-stable algorithm. If k is a single index, that value is returned; if k is a range, an array of values at those indices is returned. Note that partialsort! does not fully sort the input array.

      Examples

      1. julia> a = [1, 2, 4, 3, 4]
      2. 5-element Vector{Int64}:
      4.  2
      5.  4
      6.  3
      7.  4
      9. julia> partialsort!(a, 4)
      10. 4
      12. julia> a
      13. 5-element Vector{Int64}:
      14.  1
      15.  2
      16.  3
      17.  4
      18.  4
      20. julia> a = [1, 2, 4, 3, 4]
      21. 5-element Vector{Int64}:
      22.  1
      23.  2
      24.  4
      25.  3
      26.  4
      28. julia> partialsort!(a, 4, rev=true)
      29. 2
      31. julia> a
      32. 5-element Vector{Int64}:
      33.  4
      34.  4
      35.  3
      36.  2
      37.  1

      Base.Sort.partialsort — Function

      1. partialsort(v, k, by=<transform>, lt=<comparison>, rev=false)

      Variant of which copies v before partially sorting it, thereby returning the same thing as partialsort! but leaving v unmodified.

      source

      — Function

      1. partialsortperm(v, k; by=<transform>, lt=<comparison>, rev=false)

      Return a partial permutation I of the vector v, so that v[I] returns values of a fully sorted version of v at index k. If k is a range, a vector of indices is returned; if k is an integer, a single index is returned. The order is specified using the same keywords as sort!. The permutation is stable, meaning that indices of equal elements appear in ascending order.

      Note that this function is equivalent to, but more efficient than, calling sortperm(...)[k].

      Examples

      1. julia> v = [3, 1, 2, 1];
      3. julia> v[partialsortperm(v, 1)]
      4. 1
      6. julia> p = partialsortperm(v, 1:3)
      7. 3-element view(::Vector{Int64}, 1:3) with eltype Int64:
      8.  2
      9.  4
      10.  3
      12. julia> v[p]
      13. 3-element Vector{Int64}:
      14.  1
      15.  1
      16.  2

      source

      1. partialsortperm!(ix, v, k; by=<transform>, lt=<comparison>, rev=false, initialized=false)

      Like , but accepts a preallocated index vector ix the same size as v, which is used to store (a permutation of) the indices of v.

      If the index vector ix is initialized with the indices of v (or a permutation thereof), initialized should be set to true.

      If initialized is false (the default), then ix is initialized to contain the indices of v.

      If initialized is true, but ix does not contain (a permutation of) the indices of v, the behavior of partialsortperm! is undefined.

      (Typically, the indices of v will be 1:length(v), although if v has an alternative array type with non-one-based indices, such as an OffsetArray, ix must also be an OffsetArray with the same indices, and must contain as values (a permutation of) these same indices.)

      Upon return, ix is guaranteed to have the indices k in their sorted positions, such that

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

      The return value is the kth element of ix if k is an integer, or view into ix if k is a range.

      Examples

      1. julia> v = [3, 1, 2, 1];
      3. julia> ix = Vector{Int}(undef, 4);
      5. julia> partialsortperm!(ix, v, 1)
      6. 2
      8. julia> ix = [1:4;];
      10. julia> partialsortperm!(ix, v, 2:3, initialized=true)
      11. 2-element view(::Vector{Int64}, 2:3) with eltype Int64:
      12.  4
      13.  3

      source

      目前，Julia Base 中有四种可用的排序算法：

      InsertionSort 是一个在 QuickSort 中使用的时间复杂度为 O(n^2) 的稳定的排序算法，它通常在 n 比较小的时候才具有较高的效率。

      QuickSort 是一个内置并且非常快，但是不稳定的时间复杂度为 O(n log n）的排序算法，例如即使数组两个元素相等的，它们排序之后的顺序也可能和在原数组中顺序不一致。QuickSort 是内置的包括整数和浮点数在内的数字值的默认排序算法。

      PartialQuickSort(k) 类似于 QuickSort，但是如果 k 是一个整数，输出数组只排序到索引 k，如果 k 是 OrdinalRange，则输出数组排在 k 范围内。 例如：

      1. x = rand(1:500, 100)
      2. k = 50
      3. k2 = 50:100
      4. s = sort(x; alg=QuickSort)
      5. ps = sort(x; alg=PartialQuickSort(k))
      6. qs = sort(x; alg=PartialQuickSort(k2))
      7. map(issorted, (s, ps, qs))             # => (true, false, false)
      8. map(x->issorted(x[1:k]), (s, ps, qs))  # => (true, true, false)
      9. map(x->issorted(x[k2]), (s, ps, qs))   # => (true, false, true)
      10. s[1:k] == ps[1:k]                      # => true
      11. s[k2] == qs[k2]                        # => true

      MergeSort 是一个时间复杂度为 O(n log n) 的稳定但是非 in-place 的算法，它需要一个大小为输入数组一般的临时数组——同时也不像 QuickSort 一样快。MergeSort 是非数值型数据的默认排序算法。

      默认排序算法的选择是基于它们的快速稳定，或者 appear 之类的。对于数值类型，实际上选择了 QuickSort，因为在这种情况下，它更快，与稳定排序没有区别(除非数组以某种方式记录了突变)

      Julia选择默认排序算法的机制是通过 Base.Sort.defalg 来实现的，其允许将特定算法注册为特定数组的所有排序函数中的默认值。例如，这有两个默认算法 :

      1. defalg(v::AbstractArray) = MergeSort
      2. defalg(v::AbstractArray{<:Number}) = QuickSort

      对于数值型数组，选择非稳定的默认排序算法的原则是稳定的排序算法没有必要的（例如：但两个值相比较时相等且不可区分时）。

      By default, sort and related functions use isless to compare two elements in order to determine which should come first. The abstract type provides a mechanism for defining alternate orderings on the same set of elements. Instances of Ordering define a total order on a set of elements, so that for any elements a, b, c the following hold:

      • Exactly one of the following is true: a is less than b, b is less than a, or a and b are equal (according to ).
      • The relation is transitive - if a is less than b and b is less than c then a is less than c.

      The Base.Order.lt function works as a generalization of isless to test whether a is less than b according to a given order.

      — Type

      1. Base.Order.Ordering

      Abstract type which represents a total order on some set of elements.

      Use Base.Order.lt to compare two elements according to the ordering.

      Base.Order.lt — Function

      1. lt(o::Ordering, a, b)

      Test whether a is less than b according to the ordering o.

      Base.Order.ord — Function

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

      Construct an object from the same arguments used by sort!. Elements are first transformed by the function by (which may be ) and are then compared according to either the function lt or an existing ordering order. lt should be isless or a function which obeys similar rules. Finally, the resulting order is reversed if rev=true.

      Passing an lt other than isless along with an order other than or Base.Order.Reverse is not permitted, otherwise all options are independent and can be used together in all possible combinations.

      Base.Order.Forward — Constant

      1. Base.Order.Forward

      Default ordering according to .

      source

      — Type

      1. ReverseOrdering(fwd::Ordering=Forward)

      A wrapper which reverses an ordering.

      For a given Ordering o, the following holds for all a, b:

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

      source

      — Constant

      1. Base.Order.Reverse

      Reverse ordering according to isless.

      Base.Order.By — Type

        Ordering which applies order to elements after they have been transformed by the function by.

        Base.Order.Lt — Type

        Ordering which calls lt(a, b) to compare elements. lt should obey the same rules as implementations of .

        source

        — Type

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

        Ordering on the indices of data where i is less than j if data[i] is less than data[j] according to order. In the case that data[i] and data[j] are equal, i and j are compared by numeric value.