快速排序作为分治代表，通常实现由三步

1. 数据中选择一个元素作为”基准”（pivot），通常选取最后一个元素；
2. 分区(partition) 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
3. 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

实现过程中有两种算法可以参考，一种是需要额外空间，另外一种就是经典的原地排序，第一种效率比较低，比较容易看懂；

辅助空间

   func quickSort(data:[Int])->[Int]{
        if data.count<=1 {
            return data
        }
        
        var left:[Int] = []
        var right:[Int] = []
        let pivot:Int = data[data.count-1]
        for index in 0..<data.count-1 {
            if data[index] < pivot {
                left.append(data[index])
            }else{
                right.append(data[index])
            }
        }
        
        var result = quickSort(data: left)
        result.append(pivot)
        let rightResult = quickSort(data: right)
        result.append(contentsOf: rightResult)
        return result
    }

经典快排

   func partition( data:inout [Int],low:Int,high:Int) -> Int {
        
        let root = data[high]
        var index = low
        for i in low...high {
            if data[i] < root {
                if i != index {
                    swap(&data[i], &data[index])
                }
                index = index+1
            }
        }
        
        if high != index {
            swap(&data[high], &data[index])
        }
        return index
    }
    
    func quickSort(data:inout [Int],low:Int,high:Int) -> Void {
        if low > high {
            return
        }
        let sortIndex = partition(data: &data, low: low, high: high)
        quickSort(data: &data, low: low, high: sortIndex-1)
        quickSort(data: &data, low: sortIndex+1, high: high)
    }

测试代码:

        let data:[Int] = [1,2,3,2,4,8,9,10,19,0]
        let result = quickSort(data: data)
        print("FlyElephant方案1:-\(result)")
        
        var arr:[Int] = [10,3,17,8,5,2,1,9,5,4]
        quickSort(data: &arr, low: 0, high: arr.count-1)
        print("FlyElephant方案2:-\(arr)")

FlyElephant.png