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)快得多.
