Video在线视频

所谓排序问题

就是给定n个数字

x1 x2到xn

按照从小到大的顺序将其排列

当然 也可以按照从大到小排序

来提这个问题

二者本质上是相同的

排序问题的应用非常的广泛

对成绩单进行排序

对股票的业绩进行排序等等

不胜枚举

排序问题最简单 最常用的算法是冒泡法

在我们介绍和分析快速排序算法之前

先介绍这种经典算法以便比较

真实地体会到快速算法的快

冒泡法的基本想法

是从数列的第1个元素开始

对元素进行两两比较

如果前面的数字大于后面的数字

就交换它们的顺序 否则的话

保持原来的顺序不变

这样将全体数字扫描一遍

最右端就得到了整个数列的最大值元素

再对前n-1个元素做同样的操作

得到第二大的元素

依次进行n-1次扫描

就得到了原数列按升序排列的结果

我们用5个实际数字

演示一下冒泡法排序的实现过程

首先考查前两个数字

我们把被比较的数字用红色标出

因为5大于1

所以交换5和1的位置

再考查第2和第3个数字

因为5大于4

所以交换5和4的位置

再继续依次比较第3和第4个数字

5和2因为5大于2

所以交换这两个数的位置

最后看5和8

因为5小于8

所以这两个数字的位置保持不变

不作交换

这样所有的数字依次都扫描了一遍

数列中最大的数字

已经转移到了数列的最右边

把它固定下来

我们用彩色标出

下面对前n-1个数

也就是前4个数做同样的操作

进入第二轮比较

第二轮比较中

最后一个位置固定不变了

依次扫描前n-1个数

首先考查前两个数字

因为1小于4

所以1和4的位置不变

再考查第2,3个数字

因为4大于2

所以交换4和2的位置

再继续依次比较第3,4个数字

4和5因为4小于5

所以4和5的位置不变

这样我们得到了数列中第2大的数字

它已经被交换转移到了

数列的最右边第二个位置

把它固定下来

我们用彩色标出

5和8是数列升序排列的最后两项

下面再对还没有最终确定顺序的

剩下的前n-2个数字做同样的操作

进入第三轮比较

实际上到现在为止

这个数列的顺序已经排好了

但是算法并不知道排序已经完成

算法必须完成全部步骤

才能保证在任何情况下

都能够给出正确的排序结果

算法继续进入第3轮的比较

第三轮比较中

最后两个位置固定不变了

依次扫描前n-2个数

首先考查前两个数字

因为1小于2

所以1和2的位置不变

再考查第2,3个数字

因为2小于4

所以也不用交换

这一轮比较得到了数列中第3大的数字

把它固定下来并用彩色标出

得到4 5和8

是数列升序排列的最后三项

下面再对还没有最终确定顺序的

剩下的前n-3个数字做同样的操作

进入第四轮比较

因为n=5 n-3等于2

所以到第四轮

只剩下两个数字没有最终排定位置

比较1和2 因为1小于2

所以顺序不变

这样就得到了

整个数列最终的升序排列结果

1 2 4 5 8

冒泡法的主要优点的是非常的简单

编写很短的程序

就可以在计算机上实现

而它的主要缺陷是效率不高

对于包含几千 几万个数字的数列

计算机都可以很轻易的

马上得到排序结果

但是对于很大规模的问题

冒泡法效率低的弱点就会暴露出来

下面我们分析一下冒泡法排序的计算量

对n个数字排序

第一轮中n个元素依次两两比较

共需要n-1次比较运算

第二轮需要n-2次比较

依次直到最后第n-1轮

对剩下的两个数字进行比较

总的比较次数为n-1加n-2

一直递减加到1

等于2分之n乘n-1

也就是大约2分之n平方的比较运算

要考察和比较算法的计算效率

还要选取一台计算机

目前世界上最强大的超级计算机

已经可以达到每秒亿亿次的计算量级

对普通计算机能达到每秒万亿次

已经是很强大了

假设我们选取这样一台

每秒能够完成万亿次基本运算的计算机

也就是每秒可以完成

10的12次方量级的加 减 比较等运算

对于10的4次方

也就是1万个数字左右的规模

冒泡法排序的计算量大约是

10的8次方量级

用万亿次计算机进排序几乎不花时间

如果对100万量级的数字

也就是10的6次方量级那么多的数字

冒泡法计算量大约是

10的12次方基本运算

考虑到代码的编辑 解释

数据传输等等因素

总的运行时间

应该肯定可以在几秒之内完成

但如果问题规模继续增大

冒泡法排序的计算时间

可能就很难接受了

例如 google的搜索引擎

需要用到对10的10次方量级

那么多数字进行排序的问题

google搜索能够成功的

主要因素之一

是它能够给予每个网页一个适当的评分

评价其重要性

然后对所有网页

按照重要性评分进行排序

假设总共有100亿个网页

用一台每秒运算量达到万亿次

也就是10的12次方

基本运算的计算机来实现

10的10次方个数字

用冒泡法进行排序

需要的比较运算的次数为

2分之10的20次方

除以计算机的每秒运算量

仅仅用于比较的计算时间

就将达到2分之10的8次方秒

这是多么长的一段时间呢

我们计算一下1年有多少秒

365天乘以24小时乘以3千6百秒

1年共有31536000这么多秒

大约3.15乘以10的7次方秒

2分之10的8次秒比1年还要长

显然冒泡法对这样的问题无能为力

事实上人们早就设计出了

更高效的排序方法

最有效的应该是

上个世纪60年代初

提出的快速排序算法

我们现在引入这一部分附加内容的主题

快速排序算法

快速排序算法是一种随机化的算法

上个世纪60年代初

由英国学者霍尔提出

霍尔也因为这一贡献

荣获了1980年的图灵奖

实际上这一巧妙算法的思想

更早几年已经有苏联数学家提出

但是由于学术交流的封闭

前苏联学者的工作

没能及时让更多的人了解

人们现在广泛采用的

快速排序算法的基本形式

是霍尔独立发现的

再重复一下问题

就是要将n个不同的数字按照升序排列

注意 这里强调了n个数字互不相同

实际上如果存在一些相等的数字

也不会带来本质的困难

之所以要求n个数互不相等

主要是为了基本算法描述更方便和清晰

现在我们对算法的主要思想做一描述

首先在n个数中

随机地任选一个数

作为基准元素

将剩下的n-1个数与基准元素进行比较

大于基准元素的数放在右边

小于基准元素的数放在左边

这样基准元素的大小位置就确定了

因为比它小的数都放在它的左边

比它大的数字都放在它的右边

所以基准元素所在的位置

就是它在最终的升序排列中的位置

基准元素将全体数字分成了左右两部分

对左右两个子集合再各选一个基准元素

左边的全体数字

和左边基准元素进行比较

比左边基准元素小的放在它的左边

比左边基准元素大的放在它的右边

右边的全体数字

和右边基准元素进行比较

比右边基准元素小的放在它的左边

比右边基准元素大的放在它的右边

这时新引进的两个基准元素的位置

就是它们在最终的升序排列中的位置

此时基准元素将数列的元素

划分成了更多的部分

在每个子集中再随机选取新的基准元素

将子集内部比其小的放左边

比其大的放右边

按照这样的过程不断进行下去

这样新增的基准元素越来越多

也就是得到最终位置的元素越来越多

当所有元素都排定位置时

算法结束

下面我们还是通过一个实际的数列

演示快速排序算法的实现过程

帮助同学们真正理解快速排序算法

我们考察这样一个包含9个数字的数列

将其中数字按升序排列

快速排序算法的第一步

是在9个数字中

随机选择一个作为基准元素

假设选定的是4这个数

将它标为紫色以示区分

然后依次将3 7 8 5 2 1 9 6等

数列中的其他数字

与基准元素4进行比较

3 2 1比4小

放在了它的左边

而7 8 5 9 6比4大

放在了它的右边

经过这一步

选为基准元素的4这个数字

它在整个数列的

升序排序中的正确位置已经确定

然后进入第二步

先在3 2 1中随机选择一个数

假定选到的是1

染为绿色

将3和2依次和1比较

比1小的放左边

比1大的放右边

3和2都比1大

所以都放在了1的右边

再在7 8 5 9 6中随机选择一个数

假定选到的是8

仍然染为绿色

将7 5 9 6依次与8进行比较

比8小的是7 5 6放在了左边

比8大的是9放在了右边

这样完成了第二步

此时第二步中

选为基准元素的数字1和8

它们在最终的升序排列中的位置

也已经正确的确定了

到此为止

曾经选定为基准元素的

3个元素的位置已经确定

此时基准元素将数列划分为了3部分

分别是3 2组成的一部分

7 5 6组成的一部分

和单个数字9组成的一部分

然后进入第三步

在被先前的基准元素划分出的各部分

再各自随机地挑选一个基准元素

这一部分中比它小的放左边

比它大的放右边

假定表为蓝色的三个数3 6 9

是每一部分选定的新的基准元素

在各部分中

比基准元素小的放在它左边

比基准元素大的放在它右边

就得到了右边的结果

这时蓝色的基准元素

已经得到了它们各自的正确位置

而被基准元素划分出的各部分

至多只剩下一个数字

这些数字的位置

也已经是最终升序排列的正确位置

这时每个元素都被排定了位置

就完成了整个排序算法

为了分析快速排序算法的总的计算量

我们将一列数字表示为星号

算法过程中成为基准元素的数字

就被染上一种颜色

第1步选定1个基准元素

染为紫色

经过与其他元素进行比较后

它将整个数列划分为两部分

并且这个基准元素的位置

就是它在整个按升序排列的

最终结果中的位置

在今后的步骤中不再变化

第2步

在两部分中各选一个基准元素

得到2个新的基准元素

染为绿色

比较后已染色的元素

将整个数列划分为4部分

这2个新的绿色的基准元素的位置

就是它们在整个按

升序排列的最终结果中的位置

在今后的步骤中不再变化

第3步

在四个部分中各选一个基准元素

又得到4个新的基准元素

染为青蓝色

比较后将整个数列分为8个部分

这一步得到的4个新的基准元素的位置

也是它们在整个按升序排列的

最终结果中的位置

在今后的步骤中不再变化

这样一直做下去

每一步的新的基准元素的数目

大体上会翻倍

到第m步

大约会得到2的m-1次方个

新的基准元素

第m步后

总的基准元素的个数

可能达到1加2加2的平方

一直加到2的m-1次方个

即总和为2的m次方减1个

当这个数等于n时

就意味着所有的数字都排定了顺序

这时m大约等于log2n

因为每一步进行的比较次数不超过n次

所以排定所有数字所需的

全部比较次数不超过n乘log2n次

但是要意识到

上述分析是一种非常理想的情形

也就是每一步基准元素的个数都会翻倍

这就意味着每一个基准元素

都恰好选到了所在数据段中位数

附近大小的数字

而如果是极端坏的情况

每一次基准元都选到了最大

或最小的数字

则每一步只确定一个元素的位置

需要n-1步

才能确定所有数字的顺序位置

这时快速排序算法的计算量

就与冒泡法相同了

按照最优情况的计算量

对100亿个网页的得分进行排序

总的比较运算的次数

不超过10的10次方

乘以10倍的log2 10

用万亿次计算机计算

不会超过1秒钟

而最快情况下

快速算法的计算量与冒泡法相同

还是几乎无法有效得到排序结果

因为快速算法的执行过程

是具有随机性的

所以人们想了解

用快速排序算法对n个数字进行排序

到底运行计算量

是nlogn量级的可能性大

还是达到n平方量级的可能性大

事实上

绝大多数执行过程

是nlogn量级的计算量

只有极少数情况

会进行n平方量级的比较

而且可以证明

快速排序算法整个过程所做的

平均意义下的比较次数

是nlogn量级的

下面给出算法分析的定理和它的证明

现在证明快速排序算法

平均比较次数的分析结果

给出如下定理

假设利用随机化快速排序算法

对n个互不相同的数x1 x2

到xn进行排序

每一次都从所有可能的元素中

独立且均匀地选取基准元素

那么所做比较次数的期望

为2n倍的ln（n）

在加与n同量级的一个数

大O(n)的意思就是

与n的比值在常数范围内

下面证明这一结论

首先将x1 x2

到xn按照升序排列后的结果

表示为y1 y2到yn

也就是y1 y2到yn与x1 x2

到xn具有相同的值

并且按照升序排列

有y1小于y2小于y3等等小于yn

对于所有1到n之间不同的

两个角标i和j

假设i小于j

定义一个随机变量Xij

如果算法过程中

yi与yj进行了比较

就令Xij等于1

否则Xij等于0

这里要注意的是

在整个快速排序算法的实现过程中

每两个数之间

或者进行过1次比较

或者没有进行过比较

两个数字发生比较的时候

这两个数中间一定有一个数

是当时所考察子集中选定的基准元素

另一个数与它比较后

或者放在其左边

或者放在其右边

基准元素与子集中所有元素进行比较后

其位置即得到确定

就固定下来

今后不会再参与比较

这样总的比较次数

就可以表示为全体可能的不同的

yi和yj数对

对应的Xij的求和总数

全体不同的数对共有2分之n乘n-1个

这也说明比较次数

最多可达到2分之n乘n-1次

不会超过这个数

利用期望的线性性

即随机变量求和的期望

等于随机变量期望的求和

总的比较次数X的期望即等于

对1到n之间取值的

所有不同的数对i j

对Xij的期望求和

我们仔细考察一下Xij的期望

按照Xij的定义

它刻画的是yi与yj

是否发生过比较的情况

发生过比较Xij取值为1

否则为0

考虑升序排列y1到yn中

yi到yj的这一段数字

当yi与yj发生比较时

yi与yj中必然有一个是yi y（i+1）

直到yj这j-i+1个在升序排列中

连续出现的一段数字中的

第一个被选为基准元素的数字

因为如果yi和yj都不是这个集合中

第一个被选为基准元素的数字

那么这些数字中第一个被选为

基准元素的一定在中间的某个位置

这个基准元素一定会将

yi和yj阻隔在它的左边和右边

从而使得yi和yj

失去相互比较的机会

此时Xij必然为0

所以Xij等于1的概率

就等于从yi到yj的j-i+1个数中

选到yi或yj的概率

因为被选为基准元素是等可能的

所以这个概率等于j-i+1分之2

Xij的期望就等于j-i+1分之2

将Xij的期望表达式代入求和式

考虑到j-i+1分之2

从j等于i+1到n求和

就等于2分之2加3分之2

一直加到n-i+1分之2

所以求和式可以写成

k从2到n-i+1对k分之2求和

然后交换求和顺序

等于k从2到n

对k的不同取值

i从1到n-k+1求和

再对k求和

内层求和与i无关

对所有k

内层求和都等于

n-k+1倍的k分之2

然后进一步整理

提出2倍的n-1

再整理提出2倍的n乘k分之1

k从1到n求和

加一些剩余项

考虑到k从1到n

k分之1求和等于ln（n）

加某个常数量级的数

所以得到求和等于

2n倍的ln（n）加一个n的同阶项

这样就证明了定理结果

快速排序算法的

平均计算量是nlnn量级的

所以绝大多数情况下

它都能较快地得到排序结果