chapter2 sorting算法与算法的分析技术

《chapter2 sorting算法与算法的分析技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机算法——设计与分析导论南开大学计算机科学与技术系刘璟1Chapter2.Sorting算法与算法的分析技术2.1排序(Sorting)问题2.2O(n2)阶的排序算法2.3基于相邻元比较的排序算法和希尔(Shell)排序2.4O(nlogn)阶的排序算法2.5比较排序算法的时间复杂度下界2.6排序算法的有关研究22.1排序（Sorting）问题有关排序的几个基本概念：1.全序集：数据集合D称为关于关系“<”的全序集，如果满足1°a

2、（Sorting）问题：已知：n项记录R1，R2，…，Rn，其一个域称为关键字（Key），关键字值K1，K2，…，Kn属于一全序集。要求：重排n项记录为Rπ(1)，Rπ(2)，…，Rπ(n)，其中π：π(1)，π(2)，…，π(n)，为1,…,n的一个排列，使对应的关键字满足：Kπ(1)≤Kπ(2)≤…≤Kπ(n)。33.稳定（Stable）排序算法：如果排序问题满足：若Rπ(i)=Rπ(j)且i

3、随机存储设备上（内存）进行排序操作，这时数据间的比较和移动指令的代价一般是相同的。5.外部（External）排序算法：数据主要驻留在外部的低速存储设备（硬盘、磁带）上，数据在内存与硬盘（磁带）之间的传送、移动的代价明显高于数据比较操作，因此，外部排序算法的设计不同于内部排序。46.原址排序算法：在排序过程中除了全部输入数据所占用的空间之外，只需有限的额外空间。如果额外空间的大小与记录数n无关，则称为原址排序。7.基于关键字比较的排序算法：这类排序算法中仅对关键字进行比较和移动操作，因此关键字的比较和移动是算法的基本操作。52.2O(n2)阶的排序算

4、法2.2.1选择排序（SelectionSorting）1.选择排序的思想：把待排序的L[1..n]视为两个部分：L[1..i-1]为已排序部分，L[i..n]为未排序部分。排序步骤为：1°i=1；2°选择：在L[i..n]中求最小元L[k]，i≤k≤n；3°交换L[i]与L[k]，i++，if（i

5、中的比较次数与n个关键字的值无关，因此最坏情形和平均情形的比较总次数相同。因此，算法是O(n2)阶的。空间代价只额外占用了几个工作单元，因此，它是个原址排序算法。74.讨论：算法SelectSort按比较次数计算的最好情形时间复杂度为：如果把关键字的移动作为基本操作，情况有所不同。从算法中的if语句可看出，关键字移动min=L[j]的次数可能少于比较min>L[j]的执行次数。另外，函数Swap()需要3次移动，共3(n–1)次。因此，选择排序算法的平均移动次数会比较小，而最好情形则为3(n–1)。当数据记录比较大时，移动代价大于比较代价，选择排序也

6、可能有较好的性能。82.2.2插入排序（InsertionSorting）1.插入排序的思路：与选择排序不同，它是从无序部分不经选择，任取一元，然后插入到有序部分的正确位置上。其步骤为：L[1..n]分为两部分：L[1..i]为有序部分，L[i+1..n]为未排序部分。1°i=1；2°把L[i+1]插入到L[1..i]中的正确位置，i++；3°if(i

7、2°n个元素的所有不同的排列具有等可能性。在把L[i]插入到有序的L[1..i–1]的过程中，共有i种可能的位置，由假设2°可知落入每个位置的概率为1/i。而这i种情形所需要的比较次数分别为1，2，…，i-2，i-1，i-1，因此期望的比较次数为：10因此，插入排序虽然也是O(n2)阶的算法，但在一般情形下，会比选择排序块。算法的空间代价：基本上不需要额外空间，也是一种原址排序算法。它也是稳定的。114.讨论：在基于相邻元比较交换的排序算法中，InsertSort是最优的。如果把数据的移动作为基本操作，每一次数据比较都有一次数据移动与之对应。因此，除

8、了在外循环的n–1次移动之外，数据比较与移动次数是一致的，这与SelectSort算法是不同的。2.2.3起