快速排序(quick-sort)与前面介绍的归并排序(merge-sort)(见 算法基础——算法导论(1) )一样,使用了 分治 思想。下面是对一个一般的子数组A[p~r]进行快速排序的分治步骤:
ps: 所谓原址排序是指:我们在对组进行排序的过程中 只有常数个元素被存储到数组外面。
下面给出伪代码:
可以看出,算法的关键是partiton方法的实现。下面给出它的算法实现:
直接看可能觉得很晕,我们结合实例看看它是如何工作的:
上图(a~i)表示的是对子数组A[p~r] =[2,8,7,1,3,5,6,4]进行排序时,每次迭代之前数组元素和一些变量的值。
我们可以初步看出,在i和j移动的过程中,数组被分成了三个部分(分别用灰色,黑色,白色表示),其中i和j就是分割线,并且浅灰部分的元素均比A[r]小,黑色部分的元素均比A[r]大((i)图除外,因为循环完毕之后执行了exchange A[i+1] with A[j])。
我们再仔细分析一下具体细节:
① 首先看迭代之前的部分。它执行了x = A[r],目的是把子数组A的最后一位作为一个“基准”,其他的所有元素都是和它进行比较。它在迭代过程中值一直都没改变。然后执行i = p –基准 1,此时i在子数组A的左端。
② 再看迭代部分。迭代时j从子数组A的开头逐步移至A的倒数第二位。每次迭代中,会比较当前j位置的值和“基准”的大小,如果小于或相等“基准”,就将灰色部分的长度增加1(i=i+1),然后把j位置的值置换到灰色部分的末尾(exchange A[i] with A[j])。这样迭代下来,就能保证灰色部分的值都比“基准”小或相等,而黑色部分的值都比“基准”大。
③ 最后看迭代完成后的部分。就进行了一步 exchange A[i+1] with A[j]操作,就是把“基准”置换到灰色部分与黑色部分之间的位置。
这样所有的操作下来,就产生了一个“临界”位置q,使得A[q]大于等于A[p~q]中的每个元素,而小于等于A[q+1~r]中的每个元素。
更严格的,我们可以用以前介绍的循环不变式(见 算法基础——算法导论(1) )来证明其正确性。但由于叙述起来比较麻烦,这里就不给出了。
下面我们给出快速排序(quick-sort)算法的Java实现代码:
public static void main(String[] args) { int[] array = { 9, 2, 4, 0, 4, 1, 3, 5 }; quickSort(array, 0, array.length - 1); printArray(array); } /** * 快速排序 * * @param array * 待排序数组 * @param start * 待排序子数组的起始索引 * @param end * 待排序子数组的结束索引 */ public static void quickSort(int[] array, int start, int end) { if (start < end) { int position = partition(array, start, end); quickSort(array, start, position - 1); quickSort(array, position + 1, end); } } /** * 重排array,并找出“临界”位置的索引 * * @param array * 待重排数组 * @param start * 待重排子数组的起始索引 * @param end * 待重排子数组的结束索引 * @return */ public static int partition(int[] array, int start, int end) { int position = start - 1; int base = array[end]; for (int i = start; i < end; i++) { if (array[i] <= base) { position++; int temp = array[position]; array[position] = array[i]; array[i] = temp; } } int temp = array[position + 1]; array[position + 1] = array[end]; array[end] = temp; return position + 1; } /** * 打印数组 * * @param array */ public static void printArray(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(); }
结果:
快速排序的运行时间是跟划分密切相关的,因为划分影响着子问题的规模。
(1) 最坏情况划分
当每次划分把问题分解为一个规模为n-1的问题和一个规模为0的问题时,快速排序将产生最坏的情况(以后给出这个结论的证明,目前可以想象的出)。由于划分操作的时间复杂度为θ(n);当对一个长度为0的数组进行递归操作时,会直接返回,时间为T(0) = θ(1)。于是算法总运行时间的递归式为:
T(n) = T(n-1) + T(0) + θ(n) = T(n-1) + θ(n) 。
可以解得,T(n) = θ(n²)。
由此可见,在划分都是最大程度不平均的情况下,快速排序算法的运行时间并不比插入排序好,甚至在某些情况下(比如数组本身已按大小排好序),不如插入排序。
(2) 最好情况划分
当每次划分都是最平均的时候(即问题规模被划分为[n/2]和【n/2】-1时),快速排序性能很好,总运行时间的递归式为:
T(n) = 2T(n/2) + θ(n)
可以解得,T(n) = θ(nlg n)。
(3) 平均划分
快速排序算法的平均运行时间,更接近于最好情况划分时间而非最坏情况划分时间。理解这一点的关键就是理解划分的平均性是如何反映到描述运行时间的递归式上的。
我们举个例子,对于一个9:1的划分,乍一看,这种划分是很不平均的。此时的运行时间递归式为:
T(n) = T(9n/10) + T(n/10) + cn,
我们可以用如下递归树来更加形象地描述运行时间:
递归会在深度为log 10/9 n = θ(lg n )处终止,因此,快速排序的总代价为O(nlgn)。可见,在直观上看起来非常不平均的划分,其运行时间是接近最好情况划分的时间的。事实上,对于任何一种常数比例的划分,其运行时间总是O(nlgn)。
以上的讨论其实都做了一个前提的声明,输入数据的所有排列都是等概率的。但是事实上这个条件并不一定总是成立。正如以前介绍的,有时候我们再在算法中引入随机性,可以使得算法对所以的输入都有较好的期望性能。很多人都选择随机化版本的快速排序作为大数据输入情况下的排序算法。
与以上始终采用A[r]作为“基准”的方法不同的是,随机抽样是从子数组A[p~r]中随机的抽取一个元素,把它作为“基准”,并与A[r]交换。其他的过程与上面介绍的一致。
下面是随机化版本的算法描述:
下面给出随机化版本的Java实现代码:
public static void main(String[] args) { int[] array = { 9, 2, 4, 0, 4, 1, 3, 5 }; randomizedQuickSort(array, 0, array.length - 1); printArray(array); } public static int randomPartition(int[] array, int start, int end) { int random = (int) (Math.random() * ((end - start) + 1)) + start; int temp = array[random]; array[random] = array[end]; array[end] = temp; return partition(array, start, end); } /** * 快速排序 * * @param array * 待排序数组 * @param start * 待排序子数组的起始索引 * @param end * 待排序子数组的结束索引 */ public static void randomizedQuickSort(int[] array, int start, int end) { if (start < end) { int position = randomPartition(array, start, end); randomizedQuickSort(array, start, position - 1); randomizedQuickSort(array, position + 1, end); } }
运行结果:
在第2小节中我们给出了快速排序性能的直观分析,以及它速度比较快的原因。这一节我们要给出一个更加严谨的分析。
(1) 最坏情况分析
我们用T(n)来表示规模为n的数组采用快速排序法排序所需的时间。PARTION函数生成的两个子数组的总长度是n-1,我们设其中一个的长度为q(0 ≤ q ≤ n-1),那么另一个的长度为n-q-1,因此有递归式:
我们容易知道,上式中q在端点上取得最大值。由此我们得到:
因此,T(n) = θ(n²) + θ(n) = θ(n²);
这就是说,快速排序算法的最坏情况的运行时间是θ(n²);
(2) 期望运行时间
现在我们要求,在平均情况下,快速排序的运行时间。因此我们先对问题进行分析。
为了便于分析,不失一般性,我们将数组A的各个元素重命名为Z 1 ,Z 2 ,…Z n ,其中Z i 表示数组A中第i小的元素;此外我们还定义Z ij 表示一个包含元素Z i 到Z j (包括Z i 和Z j )的集合,即Z ij ={Z i ,Z i+1 ,…Z j }。
和 概率分析和随机算法(2)——算法导论(6) 中方式①介绍的方法一样,我们引入一个指示器随机变量X ij 来表示Z i 与Z j 是否进行了比较,即:
因为每一对元素至多被计较一次,因此我们可以很容易算出总比较次数为:
对上式两边取期望得:
下面我们来分析如何求P(z i 与z j 进行比较)。
我们先从一个简单的例子入手。考虑对一个包含数字1~10的数组A进行快速排序的情况。假设我们第一次进行PARTITION操作时,选定的“基准”元素是7,那么数组A将被划分为{1,2,3,4,5,6}和{8,9,10}两个数组,我们可以发现,这两个数组中彼此任何两个元素是不会相互比较的。因此,我们有如下断言:如果一个满足z i < X < z j (假设各元素互异)的元素x被选为“基准”后,z i 和z j 就不会被比较了;如果z i 在Z ij 的其他元素之前被选为“基准”,那么z i 会与Z ij 中的其他所有元素进行比较。于是,我们有:
进而得到:
由此我们可以得出结论:使用RANDOMIZED-PARTITION,在输入元素互异的情况下,快速排序算法的期望运行时间是O(nlgn)。