Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1793728
  • 博文数量: 438
  • 博客积分: 9799
  • 博客等级: 中将
  • 技术积分: 6092
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-25 17:25
文章分类

全部博文(438)

文章存档

2019年(1)

2013年(8)

2012年(429)

分类: C/C++

2012-04-05 14:27:56

快速排序算法合并排序算法一样,也是基于分治模式。对子数组A[p...r]快速排序的分治过程的三个步骤为:
分解:把数组A[p...r]分为A[p...q-1]与A[q+1...r]两部分,其中A[p...q-1]中的每个元素都小于等于A[q]而A[q+1...r]中的每个元素都大于等于A[q];
解决:通过递归调用快速排序,对子数组A[p...q-1]和A[q+1...r]进行排序;
合并:因为两个子数组是就地排序的,所以不需要额外的操作。

快速排序算法的伪代码:


  1. QUICKSORT(A, p, r) {
  2. 1   if p < r {
  3. 2     q = PARTITION(A, p, r);
  4. 3     QUICKSORT(a, p, q-1);
  5. 4     QUICKSORT(a, q+1, r);
  6. 5   }
  7. }

这个算法的关键在于数组的划分,即PARTITION:
  1. PARTITION(A, p, r) {
  2. 1   x = A[r];
  3. 2   i = p;
  4. 3   while j = p to r-1 {
  5. 4     if A[j] ≤ x {
  6. 5       i = i + 1;
  7. 6       swap(A[i], A[j]);
  8. 7     }
  9. 8   }
  10. 9   swap(A[i+1], A[r]);
  11. 10  return i+1;
  12. }

PARTITION直观上的看是做如下的操作:

我们给出PARTITION代码中第3行至第8行迭代的循环不变式
每一轮迭代的开始,对于任何数组下标k,有:
1) 如果p≤k≤i,则A[k]≤x。
2) 如果i+1≤k≤j-1,则A[k]>x。
3) 如果k=r,则A[k]=x。

下面便是证明这个循环不变式:
初始化:循环开始前,有i=p-1和j=p。不存在k使得p≤k≤i或i+1≤k≤j-1,所以1)和2)成立。程序第一行代码里的x=A[r]使得条件3)成立。
保持:根据第4行代码的比较结果,有两种情况:
一、A[j] > x时,仅做一个j增加1的操作,所以条件1)和3)不受影响。j增加后A[j-1]>x,又因为A[1...j-2]在迭代前同样都大于x,所以条件2)成立;
二、A[j] ≤ x时,i增加1,因为A[p...i-1]都小于等于x,而A[i]也小于等于x,所以A[p...i]都小于等于x,条件1)成立。j也增加1,与情况1一样,条件2)和条件3)也都成立。
终止:循环结束时j=r,根据条件1) A[p...i]都会小于等于x,而A[i+1...r-1]都大于x。


快速排序的性能

快速排序算法的性能与数组如何被切分有关。在最坏情况下,n个元素的数组被切分为n-1个元素和0个元素的两部分,PARTITION因为要经历n-1次迭代,所以运行代价为Ө(n)。即:
T(n) = T(n-1) + T(0) + Ө(n) = T(n-1) + Ө(n) (元素数为0时,QUICKSORT直接返回,所以运行代价为Ө(1))
利用代换法,可以得到最坏情况下快速排序算法的运行时间为Ө(n^2)

在最好情况下,每次PARTITION都得到两个元素数分别为floor(n/2)和ceiling(n/2)-1的子数组,这种情况下:
T(n) ≤ 2*T(n/2) + Ө(n)
所以最佳情况下快速排序算法的运行时间为Ө(n*lg(n))

考虑平均情况,假设每次都以9:1的例划分数组,则得到:
T(n) ≤ T(9*n/10) + T(n/10) + Ө(n)
它的递归树如下:

树的到最近的叶结点的路径长度为log_10(n),在这层之前这棵树每层都是满的,所以运行时间为cn,而越往下直至最底层log_(10/9) (n),每层的代价都会小于cn。所以以9:1划分情况下,总的运行时间
T(n) ≤ log_(10/9) (n) = O(lg(n))
事实上只要以常数比例划分数组的情况,哪怕是99:1,运行时间也仍然为O(lg(n)),只不过O记号中隐含的常量因子要大些。而一般情况下,平均下来的划分情况不应该比9:1差,直观上看来平均情况下快速算法的运行时间为O(lg(n))

稍后会对快速排序的性能做更深入的分析。


快速排序的随机化版本

因为在平均情况下,快速排序的运行时间为O(n*lg(n)),还是比较快的,所以使所有的输入都能获得较好的平均情况性能,可以使快速排序随机化,即随机选择作为分割点的元素,而不总是数组尾部的元素:


  1. RANDOMIZED_PARTITION(A, p, r) {
  2. 1    i = RANDOM(p, r);
  3. 2    swap(A[i], A[r]);
  4. 3    return PARTITION(A, p, r);
  5. }

  6. RANDOMIZED_QUICKSORT(A, p, r) {
  7. 1    if p < r {
  8. 2       q = RANDOMIZED_PARTITION(A, p, r);
  9. 3       RANDOMIZED_QUICKSORT(A, q-1, p);
  10. 4       RANDOMIZED_QUICKSORT(A, q+1, r);
  11. 5    }
  12. }


快速排序分析

前面我们从直觉上获得最坏情况下快速排序的运行时间为O(n^2),下面来证明:

设T(n)为最坏情况下规模为n的QUICKSORT的运行时间,则有:
T(n) = max<0≤q≤n-1> (T(q) + T(n-q-1) - 1) + Ө(n) (max(...)表示即所有的划分情况下,运行时间最长的情况所花费的时间)
我们猜测T(n) ≤ c*n^2成立,于是:
T(n) ≤ max<0≤q≤n-1> (c*q^2 + c*(n-q-1)^2) + Ө(n) = c * max<0≤q≤n-1> (q^2 + (n-q-1)^2) + Ө(n)

表 达式q^2 + (n-q-1)^2 在取值空间0≤q≤n-1的某个端点取得最大值,因为该表达式关于q的二阶导数是正的(即关于q的二次函数是凹的),所以max<0≤q≤n- 1>(q^2 + (n-q-1)^2) ≤ (n-1)^2 = n^2 - 2*n + 1,所以对于T(n)有:
T(n) ≤ c*n^2 - c*(2n-1) + Ө(n) ≤ n^2
因为我们可以选择足够大的常数c,使得项c*(2n-1)可以支配Ө(n),使得不等式成立,所以T(n) = O(n^2)。

同样,我们也可以证明T(n) = Ω(n^2),所以在最坏情况下快速排序的运行时间为Ө(n^2)


下面来分析一下平均情况。快速排序主要在递归地调用PARTITION过程。我们先看下PARTITION调用的总次数,因为每次划分时,都会选出一个主元元素(作 为基准、将数组分隔成两部分的那个元素),它将不会参与后续的QUICKSORT和PATITION调用里,所以PATITION最多只能执行n次。在 PARTITON过程里,有一段循环代码(第3至第8行,将各元素与主元元素比较,并根据需要将元素调换)。我们把这段循环代码单独提出来考虑,这样在每 次PATITIOIN调用里,除循环代码外的其它代码的运行时间为O(1),所以在整个排序过程中,除循环代码外的其它代码的总运行时间为O(n*1) = O(n)。

接下来分析整个排序过程中,上述循环代码的总运行时间(注意:不是某次PATITION调用里的循环代码的运行时间)。可以看 到在循环代码里,数组中的各个元素之间进行比较。设总的比较次数为X,因为一次比较操作本身消耗常量时间,所以比较的总时间为O(X)。如此整个排序过程 的运行时间为O(n+X)。

为了得到算法总运行时间,我们需要确定总的比较次数X的值。为了便于分析,我们将数组A中的元素重新命名为 z_1,z_2,z_3,...,z_n。其中z_i是数组A中的第i小的元素。此外,我们还定义Z_i_j = {z_i, z_(i+1), ..., z_j}为z_i和z_j之间(包含这两个元素)的元素集合。

我们用指示器随机变量X_i_j = I{z_i与z_j进行比较}。这样总的比较次数:
X = ∑ ∑ X_i_j
求期望得:
E[X] = E[∑ ∑ X_i_j] = ∑ ∑ E[X_i_j] = ∑ ∑ Pr{z_i与z_j进行比较}

注意两个元素一旦被划分到两个不同的区域后,则不可能相互进行比较。它们能进行比较的条件只能为:z_i和z_j在同一个区域,且z_i或z_j被选为主元元素,这样:
Pr{z_i与z_j进行比较} = Pr{z_i或z_j是从Z_i_j中选出的主元元素} = Pr{z_i是从Z_i_j中选出的主元元素} + Pr{z_j是从Z_i_j中选出的主元元素}
= 1/(j-i+1) + 1/(j-i+1) = 2/(j-i+1) (因为两事件互斥,所以概率可以直接相加)

得到x_i_j的概率后,就可以得到总的比较次数:
E[X] = ∑ ∑ Pr{z_i与z_j进行比较} = ∑ ∑ 2/(j-i+1)
设变量k = j - 1,则上式变为:
E[X] = ∑ ∑ 2/(k+1)
    < ∑ ∑ 2/k
    = ∑ O(lg(n)) (调合级数求和)
    = O(n*lg(n))

所以在平均情况下快速排序的运行时间为O(n*lg(n))

阅读(2286) | 评论(0) | 转发(7) |
给主人留下些什么吧!~~