快速排序（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 为分界点，将数列一分为二。
然后，我们按照一开始处理原数列的步骤，分别处理分解出来的两个数列，直到数列里的每一个数字都归位。
总结
快速排序的基本步骤（从小到大）：
- 在数列中选择一个数作为基准数（pivot）。
- 遍历整个数列，将所有小于基准数的数字移到基准数的左边，将所有大于基准数的数字移到基准数的右边。
- 以基准数为界，将原数列截成左右两个数列。
- 不断重复上述三个步骤来分别处理生成的两个数列，直到每个生成的数列只剩下一个数字。
在上述操作过程中，我们用到了分治和递归的思想。
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
参考文献
- 啊哈！算法
- 维基百科
