深入浅出 Swift 算法系列二：快速排序

快速排序（QuickSort）,又称为划分交换排序（partition-exchange sort），其实这个名字描述得更加形象一些。快速排序是最常用的排序，对于大的、随机数列表来说也是最快的排序。

举个例子

假设我们要将 6，1，2，7，9，3，4，5，10，8 这个数列按照从小到大的顺序进行排列。

在开始排序之前，先来观察一下按从小到大顺序排列的数列的特点：在数列中任意挑选一个数作为基准数（pivot），可以看到基准数前面的数都要比这个数小，而基准数后面的数都要比这个数小（简单的说就是前面的数小，后面的数大）。这是一个显而易见，并且十分重要的特征。接下我们将围绕这个特征设计算法。

首先，从数列里挑出一个数作为基准数。为了方便操作，这里我们选第一个数 6 作为基准数。 接下来我们的目标是把数字 6 归位，也就是说要让 6 前面的数都小于等于 6，6 后面的数都大于等于 6。

然后，我们想象有 A、B 两个指针分别指向数列的两端。

接下来的操作很简单：因为当前指针 A 指向的数字是基准数，所以我们先利用指针 B 从右往左找到一个小于 6 的数，再利用指针 A 从左往右找到一个大于 6 的数，然后交换这两个数的位置。

比如，在本文例子中，当前指针 B 指向的数字是 8，8 大于 6，继续向左移动指针 B，直到指针 B 指向数字 5 的时候停下。

现在开始向右移动指针 A，当指针 A 指向数字 7 的时候停下。

然后是非常关键的一步，交换 7 和 5 的位置。

第一次交换结束，我们继续向左移动指针 B，到 4 的位置停下。然后向右移动指针 A，到 9 的位置停下，并交换 9 和 4 的位置。

现在我们完成了第二次交换，继续向左移动指针 B，发现 3 小于 6 满足条件，停下来向右移动指针 A，指针 A 和指针 B 在 3 处相遇了。这意味我们第一轮操作即将结束。

然后将基准数 6 和 3 互相交换位置，好了现在 6 前面的数都小于等于 6，6 后面的数都大于等于 6。至此，我们完成了第一轮操作的目标——将数字 6 归位。

接下来非常重要的一步，我们以 6 为分界点，将数列一分为二。

然后，我们按照一开始处理原数列的步骤，分别处理分解出来的两个数列，直到数列里的每一个数字都归位。

总结

快速排序的基本步骤（从小到大）：

1. 在数列中选择一个数作为基准数（pivot）。
2. 遍历整个数列，将所有小于基准数的数字移到基准数的左边，将所有大于基准数的数字移到基准数的右边。
3. 以基准数为界，将原数列截成左右两个数列。
4. 不断重复上述三个步骤来分别处理生成的两个数列，直到每个生成的数列只剩下一个数字。

在上述操作过程中，我们用到了分治和递归的思想。

Swift 3 实现

var numbersArray = [1, 4, 6, 5, 8, 2]

func quicksort(left: Int, right : Int) -> Void {
    
    var i, j, pivot : Int
    
    if left > right {
        return
    }
    
    pivot = numbersArray[left]
    
    i = left
    j = right
    
    while i != j {
        
        while numbersArray[j] >= pivot && i < j {
            j -= 1
        }
        
        while numbersArray[i] <= pivot && i < j {
            i += 1
        }
        
        if i < j {
           swap(&numbersArray[i], &numbersArray[j])
        }
    }
    
    numbersArray[left] = numbersArray[i]
    numbersArray[i] = pivot
    
    //二分
    quicksort(left: left, right: i - 1)
    quicksort(left: i + 1, right: right)
}

quicksort(left: 0, right: 5)

print(numbersArray)

源代码地址

Github 地址（持续更新中，欢迎 Star）：https://github.com/Zentopia/Algorithm

参考文献

• 啊哈！算法
• 维基百科