思想

基本思想 : 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再递归每一部分，得到最后结果

步骤

1. 设置一个pivot,一般取第一个元素
2. 从后向前找一个比pivot元素小的数,交换位置(将大元素与pivot交换)
3. 从前向后找一个比pivot大的元素,交换位置(小元素与交换后的pivot位置交换.此时得到一大一小分治于pivot的两边)
4. 重复递归1.2.3步骤

代码

import Foundation
//快速排序
 @H_502_21@var unsortedList : [Int] = []
//排序20个 0-99的随机整数
 @H_502_21@for i in 0..<20 {
     unsortedList.append(Int(arc4random_uniform(UInt32(100))))
 }
@H_502_21@print("快排原始数组 : \(unsortedList)\n\n")

//统计一下快排的次数
@H_502_21@var sortCount : Int = 0

//时间复杂度为O(NlogN)
quickSort(&unsortedList,low: 0,high: unsortedList.count - 1)

//递归调用
@H_502_21@private func quickSort(_ @H_502_21@list : inout [Int],low : Int,high : Int){
    @H_502_21@if low < high {
        let prePivot = quickSortNode(&@H_502_21@list,low: low,high: high)
        quickSort(&@H_502_21@list,high: prePivot - 1)
        quickSort(&@H_502_21@list,low: prePivot + 1,high: high)
    }
}
//单次快排
@H_502_21@private func quickSortNode(_ @H_502_21@list : inout [Int],high : Int) -> Int{
    @H_502_21@var low = low
    @H_502_21@var high = high
    let pivot = @H_502_21@list[low]
    //上下未相遇
    @H_502_21@while low < high {
        //从后面找一个比pivot小的数,填入pivot位置
        @H_502_21@while low < high && @H_502_21@list[high]>=pivot {
            high -= 1
        }
        @H_502_21@list[low] = @H_502_21@list[high]
        //从前面找一个比pivot大的数,填入刚刚放入位置
        @H_502_21@while low < high && @H_502_21@list[low]<=pivot {
            low += 1
        }
        @H_502_21@list[high] = @H_502_21@list[low]
    }
    //pivot放入坑
    @H_502_21@list[low] = pivot
    //统计快排次数的
    sortCount += 1
    @H_502_21@print("第\(sortCount)次快排后的结果 result:\(list)\n")
    @H_502_21@return low
}

结果

特性