前面两种算法面临的问题，桶排序浪费存储空间，冒泡排序增加了时间的复杂度，那怎样才能既节省时间、又节省存储空间呢！
下面要讲到快速排序
举个例子
假设我们要将 6，1，2，7，9，3，4，5，10，8 这个数列按照从小到大的顺序进行排列。
从初始序列中找到一个数做为基准数，为了方便操作，这里我们选第一个数 6 作为基准数。先从右往左找一个小于 6 的数，再从左往右找一个大于 6 的数，然后交换它们。这里可以用两个变量 i 和 j，分别指向序列最左边和最右边。刚开始的时候让 i 指向序列的最左边(即 i=1)，指向数字 6。让 j 指向序列的最右边(即 j=10)，指向数字 8。
接下来，因为当前指针 i 指向的数字是基准数，所以我们先利用指针 j 从右往左找到一个小于 6 的数，再利用指针 i 从左往右找到一个大于 6 的数，然后交换这两个数的位置。
比如，在本文中，当前指针 j 指向的数字是 8，8 大于 6，继续向左移动指针 j，直到指针 j 指向数字 5 的时候停下。
现在开始让 i 往右移动指针， 当指针 i 指向数字7的时候停下
接下来最关键的一步是交换 7 和 5 的位置
第一次交换结束后，我们继续向左移动指针 j ，到 4 的位置停下。然后向右移动指针 i ，到9的位置停下，交换 i 和 j 的位置
现在我们完成了第二次交换，继续左移动指针 j 发现 3 小于6， 停下来。接着向右移动指针 i 发现此时 指针 i 和指针 j 在3处相遇，这意味着我们的第一轮位移操作即将结束
然后将基准数6和3互相交换位置， 此时的6前面的数都小于6， 6后面的数字都大于6。到此时，我们第一轮的操作已经完成。
接下来非常重要的一步是以6的分界点将数列一分为二，将左边和右边的数列分别执行上面的步骤。直到数列中的每一个数字都归位。
swift 代码实现
func quickSort(_ array: inout [Int], left: Int, right: Int) {
var i, j, pivot: Int
if left > right {
return
}
i = left
j = right
pivot = array[left]
while i != j {
while array[j] >= pivot && i < j {
j -= 1
}
while array[i] <= pivot && i < j {
i += 1
}
if i < j {
array.swapAt(i, j)
}
}
array[left] = array[i]
array[i] = pivot
quickSort(&array, left: left, right: i-1)
quickSort(&array, left: i+1, right: right)
}
参考文献 《啊哈！算法》
