算法之快速排序2基准元素的选择

一：概述

基准元素，英文是pivot，在分治的过程中，基准元素为中心，把其他的元素移动到它的左右两边。

二：具体说明

最简单的方式就是选择数列的第1个元素。

这种选择在绝大多数情况下是没有问题的。但是，假如有一个原本逆序的数列，期望排列成顺序数列，那会出现什么情况呢？

整个数列被分成了两部分，每一轮都只确定了基准元素的位置。数列的第一个元素要么是最小值，要么是最大值，根本无法发挥分治法的优势。在这种极端的情况下，快速排序需要进行n轮，时间复杂度退化成了O(n^2)。

为了避免这种情况的发生，可以采取下面的方式去解决。

其实，我们可以随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置。

这样一来，即使在数列完全逆序的情况下，也可以有效的将数列分成两部分。当然，即使是随机选择基准元素，也会有极小的几率选到数列的最大值或最小值，同样会影响到分治的效果。

所以，虽然快速排序的平均时间复杂度是O(nlogn)，但最坏的情况下的时间复杂度是O(n^2)。在后文中，为了简化步骤，省去了随机选择基准元素的过程，直接把首元素作为基准元素。