我想知道 Swift 的 sort
函数是如何实现的。它使用哪种排序算法——是归并排序、快速排序还是完全不同的算法?此函数提供的时间/复杂性保证是什么?
我在网上或官方文档中都找不到任何关于它是如何实现的说明。
最佳答案
更新 2: 正如我们在 Sort.swift 中看到的那样, sort()
现在在 Swift 5 中使用“修改后的 timsort”。Timsort是一个
... hybrid stable sorting algorithm, derived from merge sort and insertion sort ...
In the worst case, Timsort takes O(n log n) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm.
这意味着sort()
恰好是 Swift 5 中的稳定排序,但这仍然是一个实现细节。 MutableCollection.sort
文档指出
The sorting algorithm is not guaranteed to be stable. A stable sort preserves the relative order of elements that compare equal.
另见 Is sort() stable in Swift 5?在 Swift 论坛中:
The algorithm was only recently made stable in preparation for a proposal to make it guaranteed as such.
更新:Swift 现在是开源的,并且在
可以看到对集合进行排序是使用 introsort 完成的 最大递归深度为 2*floor(log_2(N))。对于少于 20 个元素的分区,它切换到插入排序,或者堆排序 如果达到递归深度。
旧答案:定义自定义 Comparable
<
中断点的结构和设置:
struct MyStruct : Comparable {
let val : Int
}
func ==(x: MyStruct, y: MyStruct) -> Bool {
println("\(x.val) == \(y.val)")
return x.val == y.val
}
func <(x: MyStruct, y: MyStruct) -> Bool {
println("\(x.val) < \(y.val)")
return x.val < y.val // <--- SET BREAKPOINT HERE
}
var array = [MyStruct]()
for _ in 1 ... 30 {
array.append(MyStruct(val: Int(arc4random_uniform(1000))))
}
sort(&array)
显示以下堆栈回溯:
(lldb) bt * thread #1: tid = 0x5a00, 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 * frame #0: 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22 frame #1: 0x00000001001cb62b sort`protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20 frame #2: 0x00000001000f5a98 sort`Swift._partition (inout A, Swift.Range) -> A.Index + 3224 frame #3: 0x00000001000f756a sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 2138 frame #4: 0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233 frame #5: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607 frame #6: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183 frame #7: 0x000000010013eaf8 sort`partial apply forwarder for reabstraction thunk helper from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56 frame #8: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475 frame #9: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157 frame #10: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29 frame #11: 0x00000001001cbdca sort`main + 42 at main.swift:0 frame #12: 0x00007fff8aa9a5fd libdyld.dylib`start + 1
以后
(lldb) bt * thread #1: tid = 0x5a00, 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1 * frame #0: 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22 frame #1: 0x00000001001cb62b sort`protocol witness for Swift._Comparable.(Swift._Comparable.Self.Type)(Swift._Comparable.Self, Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20 frame #2: 0x00000001000f449e sort`Swift._insertionSort (inout A, Swift.Range) -> () + 2958 frame #3: 0x00000001000f730e sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 1534 frame #4: 0x00000001000f797d sort`Swift._introSortImpl (inout A, Swift.Range, Swift.Int) -> () + 3181 frame #5: 0x00000001000f6c01 sort`Swift._introSort (inout A, Swift.Range) -> () + 1233 frame #6: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607 frame #7: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183 frame #8: 0x000000010013eaf8 sort`partial apply forwarder for reabstraction thunk helper from @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@unowned ()) to @callee_owned (@inout Swift.UnsafeMutableBufferPointer) -> (@out ()) + 56 frame #9: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475 frame #10: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157 frame #11: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29 frame #12: 0x00000001001cbdca sort`main + 42 at main.swift:0 frame #13: 0x00007fff8aa9a5fd libdyld.dylib`start + 1
这证实了Airspeed's answer的猜想使用了introsort 与用于较小范围的插入排序相结合。
如果数组少于 20 个元素,则似乎只使用插入排序。 这可能表明从 introsort 切换到 插入排序是 20。
当然, future 实现可能会发生变化。
关于swift - Swift 为其标准库实现了什么排序算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27677026/