快速排序算法实现

前端之家收集整理的这篇文章主要介绍了快速排序算法实现前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
@H_301_0@ 不幸的是,我没有在互联网上找到任何东西,但我确定可以找到 – 我想知道 Swift的排序算法是如何实现的.它是使用mergesort还是quicksort或其他的东西?感谢链接或答案:)
更新:Swift现在是开源的,而且在

> https://github.com/apple/swift/blob/master/stdlib/public/core/CollectionAlgorithms.swift.gyb
> https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift.gyb

可以清楚地看到,使用introsort进行排序
最大递归深度为2 * floor(log(N)),并切换到
插入排序小于20个元素的范围.

旧答案:定义可比较的结构并在断点中设置&lt ;:

  1. struct MyStruct : Comparable {
  2. let val : Int
  3. }
  4.  
  5. func ==(x: MyStruct,y: MyStruct) -> Bool {
  6. println("\(x.val) == \(y.val)")
  7. return x.val == y.val
  8. }
  9. func <(x: MyStruct,y: MyStruct) -> Bool {
  10. println("\(x.val) < \(y.val)")
  11. return x.val < y.val // <--- SET BREAKPOINT HERE
  12. }
  13.  
  14. var array = [MyStruct]()
  15. for _ in 1 ... 30 {
  16. array.append(MyStruct(val: Int(arc4random_uniform(1000))))
  17. }
  18. sort(&array)

显示以下堆栈回溯:

  1. (lldb) bt
  2. * thread #1: tid = 0x5a00,0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22,queue = 'com.apple.main-thread',stop reason = breakpoint 1.1
  3. * frame #0: 0x00000001001cb806 sort`sort. Swift.Bool + 454 at main.swift:22
  4. 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
  5. frame #2: 0x00000001000f5a98 sort`Swift._partition (inout A,Swift.Range) -> A.Index + 3224
  6. frame #3: 0x00000001000f756a sort`Swift._introSortImpl (inout A,Swift.Range,Swift.Int) -> () + 2138
  7. frame #4: 0x00000001000f6c01 sort`Swift._introSort (inout A,Swift.Range) -> () + 1233
  8. frame #5: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607
  9. frame #6: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
  10. 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
  11. frame #8: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
  12. frame #9: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157
  13. frame #10: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29
  14. frame #11: 0x00000001001cbdca sort`main + 42 at main.swift:0
  15. frame #12: 0x00007fff8aa9a5fd libdyld.dylib`start + 1

然后

  1. (lldb) bt
  2. * thread #1: tid = 0x5a00,Swift._Comparable.Self) -> Swift.Bool in conformance sort.MyStruct : Swift._Comparable + 27 at main.swift:20
  3. frame #2: 0x00000001000f449e sort`Swift._insertionSort (inout A,Swift.Range) -> () + 2958
  4. frame #3: 0x00000001000f730e sort`Swift._introSortImpl (inout A,Swift.Int) -> () + 1534
  5. frame #4: 0x00000001000f797d sort`Swift._introSortImpl (inout A,Swift.Int) -> () + 3181
  6. frame #5: 0x00000001000f6c01 sort`Swift._introSort (inout A,Swift.Range) -> () + 1233
  7. frame #6: 0x00000001000fc47f sort`Swift.sort (inout A) -> () + 607
  8. frame #7: 0x000000010013ea77 sort`partial apply forwarder for Swift.(sort (inout Swift.Array) -> ()).(closure #1) + 183
  9. 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
  10. frame #9: 0x0000000100046c4b sort`Swift.Array.withUnsafeMutableBufferPointer (inout Swift.Array)((inout Swift.UnsafeMutableBufferPointer) -> B) -> B + 475
  11. frame #10: 0x00000001000fc5ad sort`Swift.sort (inout Swift.Array) -> () + 157
  12. frame #11: 0x00000001001cb465 sort`top_level_code + 1237 at main.swift:29
  13. frame #12: 0x00000001001cbdca sort`main + 42 at main.swift:0
  14. frame #13: 0x00007fff8aa9a5fd libdyld.dylib`start + 1
  15.  

这证实了Airspeed’s answer的猜想,即使用内毒素
结合插入排序较小的范围.

如果数组具有少于20个元素,那么只有插入排序似乎被使用.
这可能表明从内部转换到的阈值
插入排序是20.

当然,实施可能会在将来发生变化.

猜你在找的Swift相关文章