chapter2 Sorting算法与算法的分析技术【荐】.ppt

计算机算法 ——设计与分析导论 南开大学 计算机科学与技术系 刘璟 Chapter 2. Sorting算法与算法的分析技术 2.1 排序(Sorting)问题 2.2 O(n2)阶的排序算法 2.3 基于相邻元比较的排序算法和希尔(Shell)排序 2.4 O(nlogn)阶的排序算法 2.5 比较排序算法的时间复杂度下界 2.6 排序算法的有关研究 2.1 排序（Sorting）问题 有关排序的几个基本概念： 1. 全序集： 数据集合D称为关于关系“”的全序集，如果 满足 1° a b，a = b，b a 三者必居其一； 2° a b，b c，则a c。 全体整数集、实数集、字符串集等都是全序集。 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)。 3. 稳定（Stable）排序算法： 如果排序问题满足：若Rπ(i) = Rπ(j) 且 i j 则π(i) π(j )，则称其为稳定排序算法。稳定排序保证序列中关键字相同的记录在排序过程中不会交换次序。 4. 内部（Internal）排序算法： 数据在高速随机存储设备上（内存）进行排序操作，这时数据间的比较和移动指令的代价一般是相同的。 5. 外部（External）排序算法： 数据主要驻留在外部的低速存储设备（硬盘、磁带）上，数据在内存与硬盘（磁带）之间的传送、移动的代价明显高于数据比较操作，因此，外部排序算法的设计不同于内部排序。 6. 原址排序算法： 在排序过程中除了全部输入数据所占用的空间之外，只需有限的额外空间。如果额外空间的大小与记录数n无关，则称为原址排序。 7. 基于关键字比较的排序算法： 这类排序算法中仅对关键字进行比较和移动操作，因此关键字的比较和移动是算法的基本操作。 2.2 O(n2)阶的排序算法 2.2.1 选择排序（Selection Sorting） 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 n ）goto 2°； 4° 停止。 2. 算法的描述 ： 输入：L[1..n]存放待排序元素，n ( ≥0 )为元素个数。 输出：L[1..n]按关键字递增顺序排列。 算法 2.1 选择排序算法 SelectSort 3. 算法的分析： 关键字的比较发生在 if 语句中，总的比较次数为： 算法中的比较次数与n个关键字的值无关，因此最坏情形和平均情形的比较总次数相同。 因此，算法是O(n2)阶的。 空间代价只额外占用了几个工作单元，因此，它是个原址排序算法。 4. 讨论： 算法SelectSort按比较次数计算的最好情形时间复杂度为： 如果把关键字的移动作为基本操作，情况有所不同。 从算法中的if语句可看出，关键字移动min = L[j]的次数可能少于比较min L[j]的执行次数。另外，函数Swap( )需要3次移动，共3( n – 1 )次。因此，选择排序算法的平均移动次数会比较小，而最好情形则为3( n – 1 )。当数据记录比较大时，移动代价大于比较代价，选择排序也可能有较好的性能。 2.2.2 插入排序（Insertion Sorting） 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 n ) goto 2°； 4° 停止。 2. 算法的描述： 算法 2.2 插入排序算法 InsertSort 3. 算法的分析： 最坏情形： 最好情形： 平均情形：设输入序列满足两个条件： 1° n个关键字值是不同的，这可以简化分析； 2° n个元素的所有不同的排列具有等可能性。 在把L[i]插入到有序的L[