快排（swift）

伪代码如下：

/**
 
 quickSort(array) {
 
 quickSort_private(array, 0, array.size-1)
   
 }

 //p,r分别代表数组的起始和终止下标，0和length-1
 quickSort_private(array, p, r) {
 //递归调用，只剩一个元素的时候返回。作为终止条件
 if p>=r return;

 let middle = partion(array, p, r)//分区的值
 quicksort_private(array, p, middle-1)//排左边
 quicksort_private(array, middle+1, r)//排右边
 
 }
 
//
 partion(array, left, right) {
 let pivot = array[right]
 var i = left
 for j in left..<right-1 {
    if array[j] < pivot {
        swap(array[i], array[j])
        i+=1
    }
 }
 swap(array[i], array[right])
 return i
 }
 
 */

实践代码如下：

public func sort(_ sourceArr: inout [Int]){
    quickSort(&sourceArr, 0, sourceArr.count-1)
}

private func quickSort(_ sourceArr: inout [Int], _ left: Int, _ right: Int) {
    guard left < right else {return}
    
    let q = partion(&sourceArr, left, right)
    quickSort(&sourceArr, left, q-1)
    quickSort(&sourceArr, q+1, right)
    
}

//分区函数
private func partion(_ sourceArr: inout [Int], _ left: Int, _ right: Int) -> Int {
    let pivot = sourceArr[right]
    var i = left
    for j in left..<right {
        if sourceArr[j] < pivot {
            if i != j {
                //自己和自己交换没有意义
                sourceArr.swapAt(i, j)
            }
            i+=1
        }
    }
    sourceArr.swapAt(i, right)
    return i
}

var targetArr = [2,3,1,5,4,9,8,0,7,6]
sort(&targetArr)
print(targetArr)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]