系列文章导航:
【从0到1学算法】二分查找法
【从0到1学算法】大O表示法
【从0到1学算法】 数组和链表
【从0到1学算法】选择排序
【从0到1学算法】递归
今天我们将学习快速排序，是最快的排序算法之一，速度比选择排序快得多！
一、分而治之
在学习快速排序前，先上开胃菜，快速排序中用到的算法--分而治之（divide and conquer, D&C，分治法）。只能解决一种问题的算法毕竟用处有限，而D&C提供了解决问题的思路。当面对新问题束手无策时，不妨自问：使用分而治之能解决吗？来个示例：假设你是农场主，有一块土地。
你要将这块土地均匀分成方块（正方形），且分出的方块要尽可能大。显然，下面的分法都不符合要求。
使用D&C解决问题分为两个步骤：
-
找出基线条件，这个条件必须尽可能简单。
-
不断将问题分解（或者说缩小规模），直到符合基线条件。
下面就来使用D&C找出解决方案。首先，找出基线条件。最容易处理的情况是，一条边的长度是另一条的整数倍。比如下图，一边是50m,另一边是25m,那么最大方块为25mx25m。
接下来是缩小问题规模，首先找出这块地可容纳的最大方块。
划出了两块640mx640m的方块，同时余下一小块地。接下来我们将继续对余下的小块地使用相同的算法。
适用于这小块地的最大方块，也适用于整块地的最大方块（可参阅欧几里算法）。问题规模缩小了，最初问题是均匀划分1680mx640m土地的问题，缩小为均匀划分640mx400m土地的问题。
接着继续缩小规模，直到满足基线条件。
余下的土地满足基线条件，160是80的整数倍，刚好将土地平分为两个方块。
因此，对于最初的土地，适用的最大方块为80mx80m。
这便是分治法，重申一下它的原理：
-
找出基线条件。（最简单的条件）
-
缩小规模，使其符合基线条件。
二、快速排序
快速排序是最快的排序算法之一，也是D&C的典范。对排序算法来说，最简单的数组是什么样子的呢？就是根本不需要排序的数组。
因此，我们的基线条件为数组为空或只包含一个元素。快速排序的步骤如下：
-
选择基准值。（可随机选择）
-
将数组分成两个子数组：小于基准值的元素和大于基准值的元素。（缩小问题规模，运用D&C）
-
对这两个子元素进行快速排序。（递归）
-
重复步骤2~3，直至子数组元素数量小于2，将子数组与基准合并（基线条件）。
换个思维想想，其实就是每轮都将基准放到正确的位置上，直至排序完成。这里有个数组为[3,5,2,1,4]假设选择3为基准，对子数组快速排序。
可能这里会有点懵，qsort([2,1])怎么操作？具体操作为如下（其实就是重复第一次的操作）：
-
选择2为基准（随机）
-
分为两个子数组，[1],[]
-
然后将子数组与基准合并，[1]+[2]+[] = [1,2] 得到有序数组
代码实现如下：
def quick_sort(arr):
# 基线条件
if len(arr) < 2:
return arr
else:
# 随机选择基准
rd = random.randint(0, len(arr) - 1)
pivot = arr.pop(rd)
# 比基准小的数组
less = []
# 比基准大的数组
greater = []
for i in range(len(arr)):
# 比基准小或等于的数放到less
if arr[i] <= pivot:
less.append(arr[i])
# 比基准小或等于的数放到greater
else:
greater.append(arr[i])
# 递归，并与基准合并
return quick_sort(less) + [pivot] + quick_sort(greater)</pre>
但我们在网上看到的，一般都不是这种写法，而是另一种，依然是开源节流的优化，不用新数组而是在数组中不断交换元素位置。代码如下：
def quick_sort(arr, start, end):
# 基线条件
if start > end:
return
# 设置一个基准
pivot = arr[start]
left = start
right = end
# 递归条件
while left != right:
# 从右边开始遍历，小于等于基准时，准备将它与左侧大于基准值的值交换
while arr[right] > pivot and left < right:
right -= 1
# 从右左开始遍历，大于基准时，准备将它与右侧小于基准值的值交换
while arr[left] <= pivot and left < right:
left += 1
if left < right:
# 将左侧大于基准值的值与右侧小于基准值的值交换
temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
# 将基准放到正确位置上
arr[start] = arr[left]
arr[left] = pivot
# 左边数组与右边数组继续快排
quick_sort(arr, start, left - 1)
quick_sort(arr, left + 1, end)</pre>
还是同样的配方：每轮都将基准放到正确的位置上，直至排序完成。
扩展：基准的选择
快速排序的性能高度依赖于选择的基准值。最坏情况下，每次划分成两个数组分别包含n-1个元素和1个元素，其时间复杂度为O(n2)。在最好的情况下，每次划分所取的基准都恰好是中值，即每次划分都产生两个大小为n/2的数组。此时，快排的时间复杂度为O(nlogn)。下面有3中基准选择方式（1）固定基准（不推荐）当待排数组有序或基本有序的情况下，很容易出现最坏情况，导致性能低下。（2）随机基准（未知待排数组有序性时，推荐）随机数算法随机选择一个元素作为划分基准，算法的平均性能较好，从而避免了最坏情况的多次发生。此时，它的平均运行时间为O(nlogn)。
# 在start和end间随机选择一元素作为划分的基准
def random(arr, start, end):
rd = random.randint(0, len(arr) - 1)
pivot = arr[rd]
# 把随机基准位置的元素和low位置元素互换
# swap交换两个元素位置的函数，这里就忽略不写了
swap(a[pivot],a[start])
return a[low]</pre>
（3）3分取值（待排数组基本有序时，推荐）选取数组开头，中间和结尾的元素，通过比较，选择中间的值作为快排的基准。这种方式能很好的解决待排数组基本有序的情况，而且选取的基准没有随机性。
def number_of_three(arr,start,end):
# 右移相当于除以2
mid = end + ((start - end) >> 1)
if arr[mid] > arr[start]:
# 把随机基准位置的元素和low位置元素互换
swap(arr[mid], arr[start])
if arr[end] > arr[start]:
swap(arr[end], arr[start])
if arr[mid] > arr[end]:
swap(arr[mid], arr[end])
# 此时，arr[mid] <= arr[end] <= arr[start]
return arr[end]</pre>
总结
-
D&C（分治法）将问题逐步分解。对问题无头绪时，可尝试使用。
-
快速排序是最快的排序算法之一，也是D&C的典范。
-
未知待排数组有序性时，推荐使用随机基准；
待排数组基本有序时，推荐使用3分取值选取基准
如果文章觉得不错，别忘了点赞、评论、转发哦！
文章首发于公众号【KEN DO EVERTHING】
本公众号专注于java相关技术,但不限于java、mysql、python、面试技巧、生活感悟等。分享优质博文,技术干货，学习资源等优质内容。
欢迎关注，一起学习，共成长！