快速排序算法

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

您对piv和pivot_location的计算是错误的。它应该是：

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

注意，在前面的计算中，我将除法移至2。

输出：

5，2，4，7，2，1，3，9，10，11，7，8 1，2，3，2，7，5，4，9，10，11，7，8 1，2，2，3，7，5，4，9，10，11，7，8 1，2，2，3，4，5，7，8，7，11，10，9 1，2，2，3，4，5，7，8，7，11，10，9 1，2，2，3，4，5，7，7，8，9，10，11

Answer 2

在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

Answer 3

如果您愿意，可以将此代码用于quickSort，代码要简洁得多，而且易于理解。试试看

func quickSort2(_ input: [Int], startIndex:Int, endIndex: Int)-> [Int] {
    var inputArray = input
    if startIndex<endIndex {
        let pivot = inputArray[endIndex]
        var index = startIndex

        for demo in startIndex..<endIndex {
            if inputArray[demo] <= pivot {
                (inputArray[index], inputArray[demo]) = (inputArray[demo], inputArray[index])
                index += 1
            }
        }
        (inputArray[index], inputArray[endIndex]) = (inputArray[endIndex], inputArray[index])
        inputArray = quickSort2(inputArray, startIndex: startIndex, endIndex: index-1)
        inputArray = quickSort2(inputArray, startIndex: index+1, endIndex: endIndex)
    }
    return inputArray
}