数据结构与算法分析课件第7章

数据结构与算法分析

APracticalIntroductionto

DataStructuresandAlgorithmAnalysis

陈星

第三部分排序和检索

第7章内排序。第8章文件管理和外排序。第9章检索。第10章索引技术。参考文献：DataStructuresandAlgorithmAnalysis，C.A.Shaffer，电子工业出版社2002。数据结构（C语言版），严蔚敏等，清华大学出版社1997。数据结构—C++与面向对象的途径，张乃孝,裘宗燕，高等教育出版社，2001。第7章内排序在计算机主存内对一组记录进行排序的标准算法。先介绍三种简单但较慢（Θ(n2)）的算法.1.插入排序。

2.起泡（冒泡排序）。

3.选择排序。再介绍几种复杂但较快的算法.

如Shell排序、快速排序、堆排序、归并排序……排序操作中的基本运算.1.比较2.交换排序方法插入类排序选择类排序交换类排序归并排序插入排序希尔排序选择排序堆排序快速排序分配类排序：基数排序起泡排序排序技术种类

按平均时间将排序分为四类：（1）平方阶(O(n2))排序

一般称为简单排序，例如直接插入、直接选择和冒泡排序（2）线性对数阶(O(nlogn))排序

如快速、堆和归并排序；

（3）O(n1+￡)阶排序

￡是介于0和1之间的常数，即0<￡<1，如希尔排序；

（4）线性阶(O(n))排序

如分配和基数排序。排序技术种类7.1排序术语及记号记录之间通过一个比较器类进行比较。关键字是数据元素中的某个数据项。每个记录中都有一个关键码域(key)。比较器类就是对该关键码进行比较;设对每一种记录类型都已定义Swap函数。思考?

有一堆杂乱无章的扑克牌,要求你从A到2的顺序在手上理好。想一想你会采用什么方法理好牌？

7.2三种代价为Θ（n2）的排序方法算法简单、易懂、易于实现，但速度慢。7.2.1插入排序原理：将无序序列中的各元素依次与前面已排序的子序列进行比较，将它插入到有序子序列中正确的位置。步骤：(1)首先将只含第1个元素的看成有序表。

(2)从线性表的第2个元素直到最后一个元素，依次将每个元素插入前面已经有序的子表中。

(3)插入第j个元素的方法：将j放在变量T中，从有序子表（原线性表的前j-1个元素）的最后一个元素开始，往前逐个与T比较，将大于T的元素无向后移一个位置，直到发现一个元素不大于T为止，将T插入到刚移出的空位置上，有序子表的长度增加为j。插入排序比较1次交换1次

比较6次交换5次比较3次交换2次比较5次交换4次比较2次交换1次比较3次交换3次比较2次交换2次比较22次交换18次

插入排序的代价分析时间代价：最差情况下(原始纪录全是逆序)：需要的比较次数：Θ(n2)

最佳情况下(原始纪录已经有序)：只需要n-1次比较；Θ(n)平均情况下：平均的时间代价是最差情况的一半，仍为Θ(n2)

空间代价：只需要一个暂存单元:Θ(1)

7.2.2起泡排序起泡排序的基本思想对所有相邻记录的关键字值进行比效，如果是逆序（a[j]>a[j+1]），则将其交换，最终达到有序化。其处理过程为：对待排序的记录序列从后向前（或从前向后）进行扫描。依次比较相邻记录的关键字。交换比较中发现的逆序。因此关键字值小的记录左移，关键字值大的记录右移。一次扫描后，最小值移动序列的顶端。做n-1遍从后向前（或从前向后）的扫描和逆序交换，或直到未发现逆序为止。起泡排序算法P144-145算法：template<classElem,classComp>voidbubsort(ElemA[],intn){for(inti=0;i<n-1;i++)for(intj=n-1;j>i;j--)if(Comp::lt(A[j],A[j-1]))swap(A,j,j-1);}教科书上有错起泡排序代价分析比较次数：时间代价：Θ(n2)

需增加一个辅助单元进行交换；空间代价：Θ(1)问：如何改进P144-145算法，减少起泡排序的比较和交换次数？7.2.3选择排序基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的办法，直到子表空为止。template<classElem,classComp>voidselsort(ElemA[],intn){for(inti=0;i<n-1;i++){intlowindex=i;//Rememberitsindexfor(intj=n-1;j>i;j--)//Findleastif(Comp::lt(A[j],A[lowindex]))lowindex=j;//Putitinplaceswap(A,i,lowindex);}}选择排序和起泡排序的比较相同：表面上来看，一轮比较和交换后，最小值都放到了顶部；实质上而言，选择排序就是起泡排序；不同：选择排序中最小元素一次交换到位；选择排序的交换次数要比起泡排序少得多。起泡排序选择排序选择排序的时间代价选择排序实质上是起泡排序。选择排序比较次数：Θ(n2)交换的次数比起泡排序少。因此，总的时间代价为Θ(n2)

。交换指针只交换指针，不移动记录本身，换来更高的效率,特别当记录很大的时候。可以降低排序算法中交换记录所需要的时间。7.2.4交换排序算法的时间代价InsertionBubbleSelectionComparisons:BestCase(n)Q(n2)Q(n2)AverageCaseQ(n2)Q(n2)Q(n2)WorstCaseQ(n2)Q(n2)Q(n2)SwapsBestCase00(n)AverageCaseQ(n2)Q(n2)(n)WorstCaseQ(n2)Q(n2)(n)这些排序方法只比较相邻的记录。交换排序的最小时间代价(平均来说):考虑一个有n个元素的序列L；L中有n(n-1)/2对不同的元素，每一对都可能是一个逆置；平均而言，一半正序，一半逆序(即每个序列有n(n-1)/4对逆置序列)；相邻元素交换只能处理掉一个逆序；任何一种将比较限制在相邻两个元素之间进行的交换算法的平均时间代价都是Q

(n2)。7.3Shell排序又称为缩小增量排序。基本思想：将整个线性表进行分割，相隔某个增量h的元素构成一个子表，对子表分别进行插入排序，并逐渐减小增量h。最后当h为1时，进行一次插入排序，排序完成。希尔排序中，确定增量的大小是关键，但迄今未能得到解决。增量序列一般取ht=n/2k(k=1,2,3,…,[logn])，其中n为待排序列的长度。

增量序列也可以以每次除以3来选取（…，121，40，13，4，1）希尔排序例子对关键字序列<07,19,24,13,31,08,82,18,44,63,05,29>

进行希尔排序：该例中n=12，[logn]=[log12]=3；取增量系列为ht=12/2k(k=1,2,3)，即h1=12/2=6,h2=12/4=3,h3=12/8≈1071924133108821844630529h1=6071824130508821944633129结果h2=3071824130508821944633129结果070508131824631929823144h3=1结果070508131824631929823144050708131819242931446382Shell排序分析相当困难，其效率依赖于增量序列的选取。可以认为Shell排序的平均时间代价为Θ(n1.5)希尔排序的空间代价为Θ(1)；同插入排序一样，希尔排序也只需要一个记录大小的辅助空间，用于暂存当前待插入的记录。当n为中等规模大小时Shell排序是不错的选择二叉查找树中序遍历有序序列888082688582

7571778880826885827177757.4快速排序分治法(divideandconquer)的思想：根结点将左、右子树分开，形成：左子树<根右子树二叉查找树中序周游可得到有序序列，但弊端多：存储占用大量结点空间、二叉树不平衡时插入时间代价大。

快速排序以一种更有效的方法实现了“分治法”思想。基本思想：从待排序序列中选取一个元素，以该关键字值为轴值(pivot)，将待排序列分割为两个子序列。轴值左侧子序列中记录都小于或等于轴值，右侧子序列中记录都大于或等于轴值。对子序列反复进行分割，直到每个子序列的元素个数为1。整个线性表变成了有序表。快速排序以60为轴值，一趟分割后结果以6为轴值，二趟分割后结果以73为轴值，二趟分割后结果关键技术：线性表的分割考虑：1、大（小）的元素要移动到表的后（前）半部分。2、在原表中移动，要考虑空位。具体步骤：附设两个指针i和j，初值分别指向第一个记录和最后一个记录，将分割中项保存在临时变量T中

，再将第一个记录移动分割中项的位置。首先从j所指位置起向前搜索，找到小于T的记录移动到i指向的位置，然后从i所指位置起向后搜索，找到大于T的记录移动到j指向的位置。重复这两步直至i=j为止。快速排序的步骤123 456783865764913273997

j

i分割中项T快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。整个表：从38，97和49中取出中项49作为分割中项T进行快速排序123 456783865764913273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。将分割中项49保存在变量T中，将i所指向的记录38移到分割中项位置。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。首先指针j指向的记录与T进行比较。97>T，不交换。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。指针j继续向前扫描。39<T。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。将39移动i所指位置。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。指针i开始向后扫描，65>T。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。将65移动j所指位置，指针j开始向前扫描。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。27<T123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。将27移动i所指位置，指针i开始向后扫描。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。76>T。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。将76移动j所指位置，指针j开始扫描。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。13<T。123 4567865763813273997123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。123 4567865763813273997将13移动i所指位置，指针i开始向后扫描。123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。123 456786576381327399738<T，不移动，指针i继续向后扫描。123 456783865764913273997

j

i分割中项T＝49快速排序的分割方法将序列38、65、76、49、13、27、39、97用快速排序的方法进行排序。123 4567865763813273997指针i和j相遇，将分割中项填入i和j所指位置。一趟分割结束。49快速排序的时间代价最佳情况:分割中项每次都为序列中记录中间值，时间代价为Θ(nlogn);最环情况:分割中项每次都为序列中记录的最大值或最小值，时间代价为Θ(n2);平均情况:平均时间代价Θ(nlogn)。快速排序的空间代价快速排序每次只能对一个子表进行排序，已划分的另一个子表需要用栈来记录下来，留待以后进行排序。通常情况下空间代价(记录子表的栈)为Θ(logn);最坏情况下空间代价为Θ(n);快速排序的优化轴值pivot的选取第一个或最后一个记录的关键字易退化为起泡算法。随机选取值开销大数组中间点三者取中法首中尾三个记录的中间值用于小子表的更佳算法划分过程没有必要划分到子表长度为1的情况，当子表长度小于某个值时，调用其他排序方法会快点。消除递归将递归改成非递归算法。速度加快。快速排序总结快速排序是一个递归的过程。在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息。快速的效率与起泡排序相比有很大地提高。在起泡排序过程中是对相邻两个记录进行关键字比较和互换的，这样每次交换记录后，只能改变一对逆序记录；而快速排序则从待排序记录的两端开始进行比较和交换，并逐渐向中间靠拢，每经过一次交换，有可能改变几对逆序记录，从而加快了排序速度。到目前为止快速排序是平均速度最快的一种排序方法，归并排序归并是指将两个或两个以上的有序表合并成一个新的有序表。归并排序的基本思想是将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，如此重复，直至得到一个长度为n的有序序列为止。归并排序的关键技术

－将两个有序序列合并为一个有序序列方法：顺序比较两个表中的元素，将值小者移入合并后的新表中，反复如此，直至所有元素都移入新表。0123 44913659776780AB0123 4567Cijk设置指针i,j,k分别指向A,B,C的第一个单元。归并排序的关键技术

－将两个有序序列合并为一个有序序列方法：设置指标，顺序比较两个表中的元素，将值小者移入合并后的新表中，反复如此，直至所有元素都移入新表。0123 44913659776780AB0123 4567Cijk7<13，移走7，指标j和k后移一位。7归并排序的关键技术

－将两个有序序列合并为一个有序序列方法：设置指标，顺序比较两个表中的元素，将值小者移入合并后的新表中，反复如此，直至所有元素都移入新表。0123 449659776780AB0123 4567Cijk

13<76，移走13，指标i和k后移一位。713归并排序的关键技术

－将两个有序序列合并为一个有序序列方法：设置指标，顺序比较两个表中的元素，将值小者移入合并后的新表中，反复如此，直至所有元素都移入新表。0123 4659776780AB0123 4567Cijk

49<76，移走13，指标i和k后移一位。71349归并排序的关键技术

－将两个有序序列合并为一个有序序列方法：设置指标，顺序比较两个表中的元素，将值小者移入合并后的新表中，反复如此，直至所有元素都移入新表。0123 49776780AB0123 4567Cijk

65<76，移走65，指标i和k后移一位。7134965归并排序的关键技术

－将两个有序序列合并为一个有序序列方法：设置指标，顺序比较两个表中的元素，将值小者移入合并后的新表中，反复如此，直至所有元素都移入新表。0123 497780AB0123 4567Cijk

76<97，移走76，指标j和k后移一位。713496576归并排序的关键技术

－将两个有序序列合并为一个有序序列方法：设置指标，顺序比较两个表中的元素，将值小者移入合并后的新表中，反复如此，直至所有元素都移入新表。0123 4977AB0123 4567Cijk

80<97，移走80。71349657680归并排序的关键技术

－将两个有序序列合并为一个有序序列方法：设置指标，顺序比较两个表中的元素，将值小者移入合并后的新表中，反复如此，直至所有元素都移入新表。0123 47AB0123 4567Cijk由于B已移空，停止比较，将A中剩余元素全部移到C中。7134965768097归并排序的伪代码Listmergesort(Listinlist){if(length(inlist)<=1)returninlist;Listl1=halfoftheitemsfrominlist;Listl2=otherhalfofitemsfrominlist;returnmerge(mergesort(l1),mergesort(l2));}template<classElem,classComp>voidmergesort(ElemA[],Elemtemp[],intleft,intright){if((right-left)<=THRESHOLD){

inssort<Elem,Comp>(&A[left],right-left+1);return;}inti,j,k,mid=(left+right)/2;if(left==right)return;mergesort<Elem,Comp>(A,temp,left,mid);mergesort<Elem,Comp>(A,temp,mid+1,right);for(i=mid;i>=left;i--)temp[i]=A[i];for(j=1;j<=right-mid;j++)temp[right-j+1]=A[j+mid];for(i=left,j=right,k=left;k<=right;k++)if(temp[i]<temp[j])A[k]=temp[i++];elseA[k]=temp[j--];}用插入排序处理较短的数组两个子数组相向插入，不需要检查子序列是否处理完成归并排序的优化实现归并排序的时/空间代价每次合并的时间代价为Θ(n)；从步长为1开始，整个合并完成需要logn次，总的时间代价为Θ(nlogn)。该时间代价并不依赖于待排数组中数值的相对顺序，因此，它也就是归并排序最佳、平均和最差的运行时间。归并排序同样也适用于处理链式存储的待排关键字序列.需要与待排序空间等量的辅助空间，空间代价为Θ(n).这是归并排序的严重缺陷。7.4堆排序堆排序耗时：初始建堆时间＋(n-1)•调整一次堆的时间。最初，堆调整的路长决定于树的深度Θ(logn)，随着选出结点的增多，待排的堆体积不断减小，调整的路长也不断减小，所以调整的时间代价最多为Θ(logn)；即堆排序总的时间为Θ(n)+(n-1)•Θ(logn)，也就是说堆排序的时间代价为Θ(nlogn)；堆排序需要一个辅助空间，即空间代价为Θ(1)。堆排序对原始记录的排列状态并不敏感，适用于规模(n)较大的待排序序列。分配排序一个简单、有效的排序:for(i=0;i<n;i++)B[A[i]]=A[i];关键码B[]用来确定一个记录在排序中的最终记录，用“盒子”来存放待排记录。这种排序方法的时间代价是(n),

但是它只能处理对一个从0到n-1的排列进行排序。扩展分配排序方法一：盒子可变长，允许关键码重复。即数组B中元素为一个链表的头结点.

关键码重复的记录在一个链表中，需要额外进行排序。方法二：允许关键码范围大于n，先将所有的A[i]放入B中，再依次从关键码B中读出记录.B的大小决定于记录的最大值MaxKeyValue.将所有记录A[i]放入B中的时间代价是(n)，从B中读出所有记录的时间代价是(MaxKeyValue)，故总时间代价是(n+MaxKeyValue)。但是,记录的规模n和MaxKeyValue之间没有任何必然联系,因此,该算法的时间代价可能为(n2)甚至更糟.分配排序的扩展桶式排序

BucketSort每一个“盒子(桶)”中存放一组相关的关键码,然后借助其他排序技术对每一个“桶”中的记录排序。分桶处理技术＋收尾排序。基数排序将排序关键字K看作是由多个关键字组成的组合关键字，即K=k1k2…kd。每个关键字ki表示关键字的一位，其中k1为最高位，kd为最低位，d为关键字的位数。例如，序列(101,203,567,231,478,352)，可以将每个关键字K看成由三个单关键字组成，即K=k1k2k3，每个关键字的取