如图所示，在分治法的思想下，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。
每一轮的比较和交换，需要把数组全部元素都遍历一遍，时间复杂度是 O(n)。这样的遍历一共需要多少轮呢？假如元素个数是n，那么平均情况下需要logn轮，因此快速排序算法总体的平均时间复杂度是O(nlogn) 。
那么基准元素是如何选的呢？又如何把其他元素移动到基准元素的两端？基准元素的选择，以及元素的交换，都是快速排序的核心问题。让我们先来看看如何选择基准元素。
基准元素的选择基准元素，英文是pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。 那么如何选择基准元素呢？
最简单的方式是选择数列的第1个元素。
这种选择在绝大多数情况下是没有问题的。但是，假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况呢？整个数列并没有被分成两半，每一轮都只确定了基准元素的位置。在这种情况下，数列的第1个元素要么是最小值，要么是最大值，根本无法发挥分治法的优势。在这种极端情况下，快速排序需要进行n轮，时间复杂度退化成了O(n2) 。
那么，该怎么避免这种情况发生呢？其实很简单，我们可以随机选择一个元素作为基准元素 ，并且让基准元素和数列首元素交换位置。这样一来，即使在数列完全逆序的情况下，也可以有效地将数列分成两
部分。当然，即使是随机选择基准元素，也会有极小的几率选到数列的最大值或最小值，同样会影响分治的效果。所以，虽然快速排序的平均时间复杂度是O(nlogn) ，但最坏情况下的时间复杂度是O(n2) 。
元素的交换选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素另一边。 具体如何实现呢？有两种方法。
1. 双边循环法。
2. 单边循环法。
何谓双边循环法？下面来看一看详细过程。给出原始数列如下，要求对其从小到大进行排序。
首先，选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素。
