Swift 快速排序算法

Question

尝试用 Swift 编写以下快速排序算法有一段时间了，但无法解决该问题。[快速排序，因为数组中有大约 15,000 个实际值]。问题是只有数组的左半部分是有序的（见图），并且该方法永远不会退出（无限循环）。从http://www.java2novice.com/java-sorting-algorithms/quick-sort/进行 Java 转换（在 Java 中测试并确实有效）。无法解决错误。

var arr = [Int]()
var length = 0

override func viewDidLoad()
{
    super.viewDidLoad()

    arr = [5,2,4,7,2,1,3,9,10,11,7,8]
    print(arr)

    sort(inputArr: &arr);

    print(arr)
}

func sort(inputArr: inout [Int])
{

    if (inputArr.count == 0) || (inputArr == nil)
    {
        print("finished")
        return
    }

    arr = inputArr
    length = arr.count
    quicksort(low:0,high:length-1)

}

func quicksort(low: Int, high: Int)
{
    var i = low
    var j = high

    var piv = (low + (high-low))
    piv = piv / 2
    let pivot_location = arr[piv]

    print("----")

    while i <= j
    {
        while arr[i] < pivot_location
        {
            i+=1
        }
        while arr[j] > pivot_location
        {
            j-=1
        }

        if i <= j
        {
            let temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp

            i+=1
            j-=1
        }
    }

    print(arr)

    if low < j
    {
        quicksort(low: low, high: j)
    }
    if i < high
    {
        quicksort(low: i, high: high)
    }
}

通过方法迭代后数组的控制台打印

Answer 1

Swift 中的快速排序：

func quicksort<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else { return a }

  let pivot = a[a.count/2]
  let less = a.filter { $0 < pivot }
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }

  return quicksort(less) + equal + quicksort(greater)
}

15.000 个随机数的基准（生成数字后计算时间）：

• 所需时间arr.filter{ $0 < $1 } ：约0.30分钟
• 问题中的代码需要：大约 1,00 分钟
• 我的答案中的快速排序需要：大约 2,00 分钟

看：

https://github.com/raywenderlich/swift-algorithm-club/tree/master/Quicksort

其他快速排序类型在这里：

https://github.com/raywenderlich/swift-algorithm-club/blob/master/Quicksort/Quicksort.swift