快速排序和高阶函数

快速排序（以下简称快排）是一种经典的排序算法，名字乍一看非常实在，细思之下却又带着点不可一世的狂傲。别的排序算法像什么插入排序、选择排序、归并排序等等，它们的名字其实都是在自解释，无非是在告诉别人我到底是怎么排的。然而快排却说，我很快，所以我叫快速排序。

你只要记住，我很快.jpg

好，在下认输。

当然，快排很快，这是真的，在实践中可以做到比归并排序快3倍以上（需要一定的优化）。快排的基本思想其实很简单，就是交换 + 分治，可以看作是对冒泡排序的一种改进。具体的我就不啰嗦了，相信大家对这个也非常熟悉了，实在不了解的同学可以先Google一下。我直接上Swift的代码好了（对我就是喜欢Swift），注释也写得很清楚：

//最坏情况(初始数组顺序或逆序): 
//T(n) = T(0) + T(n-1) + θ(n) = θ(1) + T(n-1) + θ(n) = T(n-1) + θ(n) = θ(n²)(等差级数)
//一般情况: T(n) = θ(nlgn)
func quickSort(inout list: [Int], startIndex: Int, endIndex: Int) {
    //若startIndex＜endIndex则序列至少有2个元素，其余情况(只有1个或0个)不需要排序直接返回
    guard startIndex < endIndex else {
        return
    }
    //排序，并返回参考点(参考点左侧的数都小于参考点，右侧的都大于参考点)
    let referenceIndex = divide(&list, startIndex: startIndex, endIndex: EndIndex)
    //递归，对参考点左边部分排序
    quickSort(&list, startIndex: startIndex, endIndex: referenceIndex - 1)
    //递归，对参考点右边部分排序
    quickSort(&list, startIndex: referenceIndex + 1, endIndex: endIndex)
}

上面的代码已经实现了快排的整体过程，但是divide这个函数还没有定义，下面就来实现它：

func divide(inout list: [Int], startIndex: Int, EndIndex: Int) -> Int {
    //用来记录参考点位置(遍历完成之后用来放置序列的第一个数)
    var referenceIndex = startIndex
    //参考点的值(序列中第一个元素)
    let referencePoint = list[startIndex]
    //遍历序列，与参考点比较
    for compareIndex in startIndex+1 ... EndIndex {
        //若小于参考点，就跟referenceIndex后的元素交换，referenceIndex前进一位
        if list[compareIndex] < referencePoint {
            (list[referenceIndex+1], list[compareIndex]) = (list[compareIndex], list[referenceIndex+1])
            referenceIndex++
        }
    }
    //将序列第一个元素放到参考点位置，它左边的值都比它小，右边的都比他大
    (list[startIndex], list[referenceIndex]) = (list[referenceIndex], list[startIndex])
    //返回参考点位置
    return referenceIndex
}

这样整个过程就完成了。其实上面的

if list[compareIndex] < referencePoint { 
    (list[referenceIndex+1], list[compareIndex]) = (list[compareIndex], list[referenceIndex+1]) 
    referenceIndex++ 
}

可以改为:

if list[compareIndex] < referencePoint {
    (list[referenceIndex], list[compareIndex]) = (list[compareIndex], list[++referenceIndex])
}

少了一行代码，但是不太好理解，有点得不偿失，所以还是算了。现在测试一下：

//测试数组
var testList = [3, 8, 9, 10, 2, 1]
quickSort(&testList, startIndex: 0, EndIndex: testList.count - 1)

var testList2 = [28, 3, 76, 99, 42, 111, 88, 99, 75]
quickSort(&testList2, startIndex: 0, EndIndex: testList2.count - 1)

嗯，亲测有效。

开头的代码注释上我写了快排的时间复杂度分析，在最坏情况下其实效率很低，跟冒泡选择那些『慢速』排序差不多，都是θ(n²)。造成这种情况的原因是，如果每次选择的参考点都是最小或者最大的那个，那么所谓的分治就失去了意义，因为每次遍历完序列都是把参考点单独拎出，然后剩下的数据归为一组（都比参考点大或者小），在过程中会出现n组序列，每组都要遍历一遍，效率自然低下。

基于上述思路，有一种很直接的优化方法，就是选取参考点的时候不再使用第一个元素，而是随机选取。这么做了之后，在最坏的情况下时间复杂度其实还是θ(n²)，但最坏情况的出现跟待排序的序列顺序已经无关，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到θ(nlgn)的期望时间复杂度。

要实现随机化快排，只需要在原先的divide函数开头加上这两句就行:

//获得一个在startIndex和EndIndex之间的随机数
let random = getRandomNumIn(startIndex ... EndIndex)
//将序列的第一个元素与随机参考点进行交换
(list[startIndex], list[random]) = (list[random], list[startIndex])

获取随机数的函数：

func getRandomNumIn(range: Range<Int>) -> Int {
    guard let min = range.first, let max = range.last else {
        return 0
    }
    let delta = max - min + 1
    //不能直接arc4random % delta，否则在x86、x64不同平台运行时由于字长不同会出现不可测错误
    let randomDelta = Int(arc4random() % UInt32(delta))
    let randomNum = min + randomDelta
    return randomNum
}

对外提供一个randomQuickSort函数：

func randomQuickSort(inout list: [Int], startIndex: Int, EndIndex: Int) {
    guard startIndex < EndIndex else {
        return
    }
    //排序，并返回参考点(参考点左侧的数都小于参考点，右侧的都大于参考点)
    let referenceIndex = randomDivide(&list, startIndex: startIndex, EndIndex: EndIndex)
    //递归对参考点左边部分排序
    randomQuickSort(&list, startIndex: startIndex, EndIndex: referenceIndex - 1)
    //递归对参考点右边部分排序
    randomQuickSort(&list, startIndex: referenceIndex + 1, EndIndex: EndIndex)
}

func randomDivide(inout list: [Int], startIndex: Int, EndIndex: Int) -> Int {
    let random = getRandomNumIn(startIndex ... EndIndex)
    (list[startIndex], list[random]) = (list[random], list[startIndex])
    
    return divide(&list, startIndex: startIndex, EndIndex: EndIndex)
}

好了，快排讲完了。接下来讲讲高阶函数。高阶函数简单来说呢，就是函数可以作为变量、参数、返回值等等，总之函数是一等公民。Swift是一个多范式语言，具有一些函数式语言的特性，函数自然便是一等公民。下面我还是以快排代码为例来解释一下。之前我们的quickSort跟divide是两个独立的函数，quickSort在内部调用divide函数的时候需要传一堆参数。而且 divide这个函数可能被别的函数调用，或者被直接使用，如果传入的序列跟 quickSort使用的是同一个的话，序列就有可能被意外地多次改变，不能被正确排序。这种情况下，我们可以把divide定义在quickSort内部:

func customQuickSort(inout list: [Int], startIndex: Int, EndIndex: Int) {
    let divide: () -> Int = {
        //用来记录参考点位置(遍历完成之后用来放置序列的第一个数)
        var referenceIndex = startIndex
        //参考点的值(序列中第一个数)
        let referencePoint = list[startIndex]
        //遍历序列，与参考点比较
        for compareIndex in startIndex+1 ... EndIndex {
            //若小于参考点，就跟referenceIndex后的数交换，referenceIndex前进一位
            if list[compareIndex] < referencePoint {
                (list[referenceIndex], list[compareIndex]) = (list[compareIndex], list[++referenceIndex])
            }
        }
        //将序列第一个数放到参考点位置，它左边的值都比它小，右边的都比他大
        (list[startIndex], list[referenceIndex]) = (list[referenceIndex], list[startIndex])
        //返回参考点位置
        return referenceIndex
    }
    
    //startIndex==EndIndex表明这一部分已排序完成
    guard startIndex < EndIndex else {
        return
    }
    //排序，并返回参考点(参考点左侧的数都小于参考点，右侧的都大于参考点)
    let referenceIndex = divide()
    //递归对参考点左边部分排序
    customQuickSort(&list, startIndex: startIndex, EndIndex: referenceIndex - 1)
    //递归对参考点右边部分排序
    customQuickSort(&list, startIndex: referenceIndex + 1, EndIndex: EndIndex)
}

divide内部的代码跟之前完全一样，但是它现在是被声明为一个局部变量，只能在quickSort内部被调用，而且不需要接受参数。这个时候已经不能叫它函数了，而应该叫闭包。闭包简单来讲就是一个带有上下文环境的函数，在这个例子中，divide可以捕获外部函数customQuickSort中的变量。其实换个说法就是在调用它的时候，如果在它自己内部找不到某个变量，它就会到它外部函数中去寻找。闭包是一个引用类型，它持有上下文环境的方式也是通过引用，搞清楚这个可以避免很多错误。

好了，快排有了，但如果有人还想使用随机化快排呢，而且他不想用我提供的获取随机数据的函数，而是想要用自己的，那该怎么办呢？这种情况下，我们稍微改一下customQuickSort，让它额外接收一个可空闭包作为参数，这个闭包用来获取一个随机索引，如果闭包不为空，就在divide中调用闭包，并将获取的随机索引所在的元素与序列的第一个元素交换，这样这个随机元素在接下来的过程中将作为参考点使用。稍微修改一下上面的代码：

func customQuickSort(inout list: [Int], startIndex: Int, EndIndex: Int, randomHandler: ((range: Range<Int>) -> Int)?) {
    let divide: () -> Int = {
        if let getRandom = randomHandler {
            let randomIndex = getRandom(range: startIndex ... EndIndex)
            (list[startIndex], list[randomIndex]) = (list[randomIndex], list[startIndex])
        }
    //剩余代码不变

调用：

//基本快排
customQuickSort(&testList2, startIndex: 0, EndIndex: testList2.count - 1, randomHandler: nil)
//随机化快排，自己传入一个获取随机数的闭包，我这边使用了原先定义好的那个
customQuickSort(&testList2, startIndex: 0, EndIndex: testList2.count - 1) { (range) -> Int in
    return getRandomNumIn(range)
}

这样一来，使用起来就灵活了很多。完整的代码可以看这里。

---

注：文中的EndIndex为笔误，函数参数首字母不应该大写，改为endIndex。github上的代码已更新。