排序及相关函数

Julia 拥有为数众多的灵活的 API，用于对已经排序的值数组进行排序和交互。默认情况下，Julia 会选择合理的算法并按标准升序进行排序：

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

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

  1. julia> sort([2,3,1], rev=true)
  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 关键字指定关系。

排序函数

  1. Base.sort!
  2. Base.sort
  3. Base.sortperm
  4. Base.InsertionSort
  5. Base.MergeSort
  6. Base.QuickSort
  7. Base.PartialQuickSort
  8. Base.Sort.sortperm!
  9. Base.Sort.sortslices

排列顺序相关的函数

  1. Base.issorted
  2. Base.Sort.searchsorted
  3. Base.Sort.searchsortedfirst
  4. Base.Sort.searchsortedlast
  5. Base.Sort.insorted
  6. Base.Sort.partialsort!
  7. Base.Sort.partialsort
  8. Base.Sort.partialsortperm
  9. Base.Sort.partialsortperm!

排序算法

目前，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 来实现的，其允许将特定算法注册为特定数组的所有排序函数中的默认值。例如，这有两个默认算法 sort.jl:

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

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

Alternate orderings

By default, sort and related functions use isless to compare two elements in order to determine which should come first. The Base.Order.Ordering 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 isequal).
  • 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.

  1. Base.Order.Ordering
  2. Base.Order.lt
  3. Base.Order.ord
  4. Base.Order.Forward
  5. Base.Order.ReverseOrdering
  6. Base.Order.Reverse
  7. Base.Order.By
  8. Base.Order.Lt
  9. Base.Order.Perm