快速排序（快排Swift）

快速排序.jpg

快排Swift代码如下，如果有疑问欢迎讨论~

import Cocoa

class Sort {
    
    /*
     * array：传入参数的数组，注意是传址不是传值
     * p:排序区间起点下标
     * r:排序区间终点点下标
     */
    private func partition(_ array:inout [Int], _ p:Int, _ r:Int) -> Int {
        
        let pivot = array[r] // 分界值，一般选数组排序区间末尾元素
        
        var i:Int = p
        for j in p...r-1 {
            
            if array[j] < pivot{ 
                array.swapAt(i, j) // 交换数组下标为 i、j 的元素                
                i += 1 // 有小于pivot的数字i++
            }
        }
        
        // 交换 a[i] 与 a[r] 即：将pivot放到相应位置
        array[r] = array[i]
        array[i] = pivot
        
        return i // 获取分界值(pivot)排序后下标
    }
    
    /* array：传入参数的数组，注意是传址不是传值
     * p:排序区间起点下标
     * r:排序区间终点点下标
     */
    private func qucikSortC (_ array:inout [Int], _ p:Int, _ r:Int) -> [Int]{
        // 需要排序的区间只包含一个数字，则不需要重排数组，直接返回
        if p >= r {
            return array
        }
       
        let i = partition(&array, p, r)

        qucikSortC(&array, p, i-1)
        qucikSortC(&array, i+1, r)
      
        return array
    }
    
    public func quickSort(_ array: [Int]) -> [Int] {
        var a = array
        return  qucikSortC(&a, 0, array.count-1)
    }
    
}

测试用例：

var sort = Sort()
let result = sort.quickSort([6,11,3,9,8])
print(result)

控制台输出

[3, 6, 8, 9, 11]

注：
1，传参部分要传址，对原数组原地排序，也方便方法的return
2，partition()函数部分，交换代码循环结束后，还需要将分解值放入到准确对应的下标 i 处