算法图解系列之快速排序[04]

4 快速排序
4.1 分而治之的思想<D&C>

// TODO: 工作原理
// FIXME: 1. 找出简单的基线条件
// FIXME: 2. 确定如何缩小问题规模, 使其符合基线条件
/** PS: D&C并非算法, 而是一种思想 */

e.g.

/*
 案例: 给定一个数组[2, 4, 6], 计算出数组所有元素之和
 */

/// 解题思路, 1) 使用循环 2) 递归

// TODO: 1. 使用循环的方式解决
func sum1(_ arr: Array<Int>) -> Int {
    var result = 0
    guard arr.count > 0 else {
        print("array is nil!")
        return 0
    }
    
    for idx in 0 ..< arr.count {
        result += arr[idx]
    }
    
    return result
}

// TODO: 2. 那么如何使用递归的方式完成这种任务呢?
// FIXME: 1. 首先, 要找到基线条件. 此题中, 最简单的数组是什么样的呢？ (答: 空数组)
// FIXME: 2. 基线条件确定了, 接下来就简单了. 我们只要把数组像空数组靠近即可.
func sum2(_ arr: Array<Int>) -> Int {
    var tmp = arr
    // 基线条件, 当数组为空时, 结束递归调用
    guard tmp.count > 0 else {
        return 0
    }
    
    var result = tmp.last!
    // 使数组每次减少一个元素, 向空数组接近
    tmp.removeLast()
    result += sum2(tmp)
    
    return result
}

let arr = [2, 3, 5, 7 ,1]
print(sum2(arr))

print("The value of atNone: \(atNone)")

// 二分查找
func binarySearch(arr: Array<Int>, target: Int) -> Int {
    var low = 0
    var high = (arr.count - 1) / 2
    var idx = -1
    var searchCount = 0
    // 基线条件1(low < high)
    while low < high {
        searchCount += 1
        // 基线条件2(找到结果)
        if target == arr[high] {
            idx = high
            break
        }
        
        if target > arr[high] {
            low = high
            high = arr.count - 1
        }else {
            high /= 2
        }
    }
    print("Search count is: \(searchCount)")
    return idx
}

print("Target index is :\(binarySearch(arr: arr, target: 3))")

4.3.2 平均情况 & 最糟情况

// MARK: - 4.3.2 平均情况 & 最糟情况
// FIXME: 1. 平均情况: O(n * logn)
// 1) logn 代表: 最佳情况下, 要遍历logn层
// 2) n 代表: 每层都需要遍历n个元素
/*
 e.g.
 数组[7, 3, 1, 4, 11, 19, 9] 包含7个元素. 排序之后的结果为[1, 3, 4, 7, 9, 11, 19]
 如果随机选择的索引对应的值刚好为中间值(类似于二分查找的情况), 那么这时所需要排序的层级即为O(logn)
 若总是选取剩余数组的第0个索引:
 第一层: 以[0]为基准值. [7, 3, 1, 4, 11, 19, 9]
 第二层: 以[0]为基准值. less: [3, 1, 4]  greater: [11, 19, 9]
 第三层: ...        . l: [1] g: [4]    l: [9] g: [19]

 */
// FIXME: 以上为最佳情况, 遍历层级为3, 即logn. 但是每层所需要遍历的元素都是n(即需要遍历整个数组的所有元素).

// FIXME: 2. 最糟情况: O(n * n)
// 1) n 代表: 需要遍历n层
// 2) n 代表: 每层都需要遍历n个元素

4.4 快速排序实现

// MARK: - 快速排序代码实现
func quickSort(_ arr: Array<Int>) -> Array<Int> {
    let tmp = arr
    // 基线条件
    guard tmp.count > 1 else {
        return tmp
    }
    
    let base = tmp[0]
    var less = Array<Int>()
    var greater = Array<Int>()
    var result = Array<Int>()

    // 递归条件
    for idx in 0 ..< tmp.count {
        if tmp[idx] < base {
            less.append(tmp[idx])
        } else if tmp[idx] > base {
            greater.append(tmp[idx])
        }
    }
    
    result.append(contentsOf: quickSort(less))
    result.append(base)
    result.append(contentsOf: quickSort(greater))
    return result
}

let quickSortArray = [7, 3, 1, 4, 11, 19, 9]
print(quickSort(quickSortArray))

4.4 小结

// MARK: - 小结
// FIXME: 1. D&C将问题逐步分解. 使用D&C处理列表时, 基线条件很可能是空数组或者只包含一个元素的数组.
// FIXME: 2. 实现快速排序时, 请随机的选择用作基准值的元素. 快速排序的平均运行时间为O(nlogn)
// FIXME: 3. 大O表示法的常量有时事关重大, 这就是快速排序比合并排序快的原因所在.
// FIXME: 4. 比较简单查找和二分查找时, 常量几乎无关紧要, 因为列表很长时, O(logn)比O(n)快得多.