快速排序 Swift之Array.filter(高阶函数)实现

原理:

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤：

• 从数列中挑出一个元素，称为"基准"（pivot）

• 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）

• 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

1、通俗解法

func quickSort(array: [Int]) -> [Int] {
    if array.count <= 1 {
        return array
    }
    let left = array.filter { (item) -> Bool in
        return item < array[0]
    }
    let middle = array.filter { (item) -> Bool in
        return item == array[0]
    }
    let right = array.filter { (item) -> Bool in
        return item > array[0]
    }
    return quickSort(array: left) + middle + quickSort(array: right)
}

var a = [5, 8, 5, 7, 41, 2, 43, 6, 601, 61, 52, 33, 6, 7, 61, 1, 3, 6, 31, 2, 30, 6]
let b = quickSort(array: a)
print(b) // [1, 2, 2, 3, 5, 5, 6, 6, 6, 6, 7, 7, 8, 30, 31, 33, 41, 43, 52, 61, 61, 601]

2、极简实现

func quickSort(_ a: [Int]) -> [Int] {
    if a.count <= 1 { return a }
    return quickSort(a.filter({$0 < a[0]})) + a.filter({$0 == a[0]}) + quickSort(a.filter({$0 > a[0]}))
}

缺点

• 临时变量（left middle right）空间浪费
• quickSort 内部一次循环变为三次 时间浪费
• 排序后的数组不是原来的数组了