排序和相關函式

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 都不小於對方，則 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)，將會取用相同的切片，但結果順序會是 row-major。

更高維度的範例

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 必須根據關鍵字定義的順序排序。在傳回的索引中 insert! 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 之前複製 v，因此傳回與 partialsort! 相同的內容，但不會修改 v。

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

傳回向量 v 的局部排列 I，以便 v[I] 傳回索引 k 處 v 的完全排序版本的值。如果 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 有非以 1 為基礎索引的替代陣列類型，例如 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 是否根據排序 o 小於 b。

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

從 sort! 使用的相同參數建構 Ordering 物件。元素會先由函數 by（可能是 identity）轉換，然後根據函數 lt 或現有排序 order 進行比較。lt 應該是 isless 或遵守與 sort! 的 lt 參數相同的規則的函數。最後，如果 rev=true，則會反轉產生的順序。

傳遞 isless 以外的 lt 以及 Base.Order.Forward 或 Base.Order.Reverse 以外的 order 是不允許的，否則所有選項都是獨立的，並且可以一起用於所有可能的組合中。

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，其中如果 data[i] 小於 data[j]（根據 order），則 i 小於 j。如果 data[i] 和 data[j] 相等，則以數值比較 i 和 j。