T13-基于线性表的排序算法

基于线性表的排序算法第七章主讲：周翔回顾请简述索引顺序查找的算法思想。请思考如何处理哈希冲突。预习检查请描述一下冒泡排序的算法思想。请描述一下堆排序的算法思想。本章目标3磁盘排序重点了解掌握2归并排序基数排序交换排序插入排序选择排序1排序的基本概念什么是排序：排序的定义：对于计算机中存储的数据来说，排序就是将一组“无序”的记录，通过一定的方式，按照某种关键字顺序排列调整为“有序”的记录，从而提高数据查找的效率。概括：将一组杂乱无章的数据按一定规律顺次排列起来。排序的目的是什么？便于查找！排序的基本概念排序的分类：根据数据存储位置的不同，排序可分为内部排序和外部排序：若所有需要排序的数据都存放在内存中，在内存中调整数据的存储顺序，这样的排序称为内部排序；若待排序记录数据量较大，排序时只有部分数据被调入内存，排序过程中存在多次内、外存之间的交换，这样的排序称为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。排序的基本概念在排序过程中，一般进行两种基本操作：比较两个关键字的大小；将记录从一个位置移动到另一个位置。对于第二种操作，需要采用适当地存储方式：顺序结构链表结构记录顺序与地址顺序结合的表示方法我们重点来讨论在顺序存储结构上各种排序方法的实现。排序的基本概念排序算法的好坏如何衡量？

空间效率占内存辅助空间的大小稳定性A和B的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。时间效率排序速度（比较次数与移动次数）排序的基本概念假设Ki是Ri的主关键字，Kj是Rj的主关键字稳定排序：若Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，在排序前的序列中Ri领先于Rj(即i<j)，经过排序后得到的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；不稳定排序：反之，当相同关键字的领先关系在排序过程中发生变化者，则称所用的排序方法是不稳定的。…ai…aj…排序后…ai…aj…稳定排序…aj…ai…排序后…ai…aj…不稳定排序插入排序插入排序（insertionsort）可以视为两步操作，一步是插入，一步是排序。插入排序的基本思想就是将一条记录插入到一组已经有序的序列中，继而得到一个有序的、数据个数加一的新的序列。插入排序不同的具体实现方法导致不同的算法描述：直接插入排序（基于顺序查找）折半插入排序（基于折半查找）希尔排序（基于逐趟缩小增量）插入排序——直接插入排序有序序列R[1..i-1]R[i]

无序序列R[i..n]有序序列R[1..i]无序序列R[i+1..n]插入排序——直接插入排序21254925*16080123456012345

6214925*1608i=20123456212525*1608i=3无序数组＞49＞监视哨25插入排序——直接插入排序25*2125491608012345

6012345621254925*08i=5012345621254925*16i=6i=4<=<<1608插入排序——直接插入排序直接插入排序算法{48}62357755143598{4862}357755143598{354862}7755143598{35486277}55143598{3548556277}143598{143548556277}3598{14353548556277}98{1435354855627798}

稳定的排序方法插入排序——直接插入排序算法描述：步骤1：在R[1..i-1]中查找R[i]的插入位置，

R[1..j].keyR[i].key<R[j+1..i-1].key步骤2：将R[j+1..i-1]中的所有记录均后移一个位置

步骤3：将R[i]插入到R[j+1]的位置上插入排序——直接插入排序直接插入排序算法的要点是：使用监视哨r[0]临时保存待插入的记录。从后往前查找应插入的位置。查找与移动用同一循环完成。直接插入排序算法分析：从空间角度来看，它只需要一个辅助空间r[0]。从时间角度来看，主要时间耗费在关键字比较和移动元素上。比较次数和移动次数与初始排列有关

插入排序——直接插入排序最好的情况：总的比较次数：总的移动次数：最坏的情况：总的比较次数：总的移动次数：顺序排列逆序排列n-1次2(n-1)次

插入排序——直接插入排序直接插入排序算法分析：若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况，则平均情况比较次数和移动次数为n2/4时间复杂度为O(n2)空间复杂度为O(1)是一种稳定的排序方法插入排序——直接插入排序折半插入排序直接插入排序减少关键字间的比较次数在插入r[i]时，利用折半查找法寻找r[i]的插入位置插入排序——折半插入排序折半插入排序（binaryinsertionsort）是对直接插入排序的改进。在直接插入排序中，主要的时间消耗在数据的比较和移动上，那么可以在前半部分有序序列中采用折半查找的方法来提高查找速度。插入排序——折半插入排序i=2插入排序——折半插入排序i=3插入排序——折半插入排序i=4插入排序——折半插入排序i=5插入排序——折半插入排序i=6插入排序——折半插入排序算法分析：折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。

它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第i个对象时，需要经过

log2i

+1次关键码比较，才能确定它应插入的位置。当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列插入排序——折半插入排序算法分析：减少了比较次数，但没有减少移动次数平均性能优于直接插入排序空间复杂度为O(1)是一种稳定的排序方法时间复杂度为O(n2)插入排序——希尔排序

又称缩小增量排序法利用直接插入排序的最佳性质：在基本有序时，效率较高在待排序的记录个数较少时，效率较高希尔排序的基本思想是：先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。插入排序——希尔排序例：关键字序列T=(49，38，65，97,76,13,27,49*，55,04）：380123456789104938659776132749*5504初态：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697r[i]dk

值较大，子序列中对象较少，速度较快；dk

值逐渐变小，子序列中对象变多，但大多数对象已基本有序，所以排序速度仍然很快。插入排序——希尔排序算法分析：技巧：子序列的构成不是简单地“逐段分割”将相隔某个增量dk的记录组成一个子序列让增量dk逐趟缩短（例如依次取5,3,1）直到dk＝1为止。优点：小元素跳跃式前移最后一趟增量为1时，序列已基本有序平均性能优于直接插入排序时间复杂度是n和d的函数：O(n1.25）～O（1.6n1.25）—经验公式空间复杂度为O(1)是一种不稳定的排序方法遗留问题：如何选择最佳序列，目前尚未解决最后一个增量值必须为1，无除1以外的公因子不宜在链式存储结构上实现交换排序交换排序（swapsorting）的核心思想：是根据序列中两条记录键值的比较结果，判断是否需要交换记录在序列中的位置。其特点是将键值较大（或较小）的记录向序列的前端移动，将键值较小（或较大）的记录向序列的后端移动。交换排序基本思想：通过交换逆序无素进行排序的方法。冒泡排序快速排序交换排序——冒泡排序（相邻比序法）基本思想：反复扫描待排序记录序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序则交换位置。将待排序的记录看成坚着排列的“气泡”，键值较重的记录比较重,从而往下沉。交换排序——冒泡排序（相邻比序法）以升序为例第一趟i=121254925*1608012345

6j=5j=4j=3j=2j=121<2525<4949>25*49<1649<08第一趟扫描结束：关键字最大的记录沉到最底下！（n的位置）交换排序——冒泡排序（相邻比序法）第二趟i=221<2525=25*25*<1625*<08212525*1608012345

6j=4j=3j=2j=149第二趟扫描结束：关键字次大的记录沉到n-1位置！交换排序——冒泡排序（相邻比序法）第三趟i=321<2525>1625>08第三趟扫描结束：记录沉到n-2位置！j=3j=2j=121251608012345

64925*交换排序——冒泡排序（相邻比序法）第四趟i=421>16第四趟扫描结束：记录沉到n-3位置！21>08j=2j=1211608012345

64925*25交换排序——冒泡排序（相邻比序法）第五趟i=516>08第五趟扫描结束：记录沉到n-4位置！j=11608012345

64925*2521最后一个元素一定是关键字最小的元素：交换排序——冒泡排序（相邻比序法）254925*160801234521所以，n个记录，需扫描n-1趟，即可完成排序最好的情况：总的比较次数：总的移动次数：最坏的情况：总的比较次数：总的移动次数：顺序排列逆序排列n-1次O(n)交换排序——冒泡排序（相邻比序法）

交换排序——冒泡排序（相邻比序法）算法分析：时间复杂度为O(n2)空间复杂度为O(1)是一种稳定的排序方法算法思想：任取一个元素(如第一个)为中心所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个交换排序——快速排序21254925*16080123452125*1625160849pivotkey0821pivotkeypivotkey25*2549交换排序——快速排序49081625*2521081625*212549pivotkey交换排序——快速排序012345678493838656597977676131327274949highlow49界点交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序38659776132749highlow49界点0123456784938659776132749交换排序——快速排序交换排序——快速排序对以下实例进行快速排序（以第一个元素作基准）：

4862357755143598第一次划分：{35

1435}48{5577

62

98}第二次划分：{14}35{35}4855{77

62

98}第三次划分：1435354855{62}77{98}交换排序——快速排序快速排序也可以以最后一个元素作为基准，对以下实例进行快速排序（以最后一个元素作基准）：

4862357755143598第一次划分：{14}35{3577556248}

98第二次划分：1435{35}48{5562

77}98第三次划分：14353548{5562}7798第四次划分：14353548{55}627798算法分析：每一趟的子表的形成是采用从两头向中间交替式逼近法由于每趟中对各子表的操作都相似，可采用递归算法可以证明，平均计算时间是O(nlog2n)实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low和hi