快速排序

快速排序是对一个待排序的数组，从中取出一个元素作为key，其它元素一一与之比较，并调换位置，分成左边是数据更小的一半和右边是更大的一半；再对左边一半和右边一半故技重施，直到两边的一半不可分割，最终得到这个有序数组。

快速排序.gif

下面是Swift的实现

func sorting(arr: inout [NSInteger], begin : NSInteger, end : NSInteger) {
        
    if arr.count <= 1 || arr.count < begin || arr.count < end ||  begin >= end {
        return
    }
         
    let key = arr[begin]
    var i = begin
    var j = end
    while i<j {
        // 先让j从末端开始找比key小的数
        while i<j && arr[j] > key {
            j = j - 1
        }
        if i != j {// 存在j位置比i位置数据小，需调换位置
            arr[i] = arr[j]
            arr[j] = key
            i = i + 1
        }
        // 交换完位置后，需要从开始的位置i+1寻找比key大的数据
        while i<j && arr[i] < key {
            i = i + 1
        }
        if i != j {// 找到了前面数据比key大的情况
            arr[j] = arr[i]
            arr[i] = key
            j = j - 1
        }
    }
    print("经过key=\(key)排序后的数组：\(arr)");
    // 上面循环结束后就完成了一次分割， 接下来对分割后的部分重新排序
    sorting(arr: &arr, begin: 0, end: i-1)
    sorting(arr: &arr, begin: i+1, end: end)
}

测试代码

let arrToSort : [NSInteger] = [16, 1, 9, 11, 5, 3, 8, 17, 10]

guard arrToSort.count > 0  else {
    return
}

var result : [NSInteger] = NSMutableArray.init(array: arrToSort) as! [NSInteger]
    
sorting(arr: &result, begin: 0, end: arrToSort.count-1)
    
print("排序后的数组结果为：\(result)")
    

输出结果为：

排序后的数组结果为：[1, 3, 5, 8, 9, 10, 11, 16, 17]

时间复杂度空间复杂度：
时间复杂度： 𝑂(𝑛𝑙𝑜𝑔𝑛) ~ O(n²)，空间复杂度：𝑂(𝑙𝑔𝑛)

归并排序的时间复杂度：𝑂(𝑛𝑙𝑜𝑔𝑛) 空间复杂度：𝑂(𝑛𝑙𝑜𝑔𝑛)