排序(网络版).ppt

《排序(网络版).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第15章排序1排序的基本概念插入排序快速排序选择排序归并排序基数排序主要内容排序：将一个数据元素（记录）的任意序列，重新排列成一个按关键字有序的序列。设：R1，R2，R3，…，Rn是n个记录，k1，k2，k3，…，kn为它们的关键字，排序就是将记录按关键字递增（或递减）的次序排列起来。常见的排序结果递增：kiki+1非递减：ki≤ki+1非递增：ki≥ki+115.1排序的基本概念排序分类按照排序记录所在的位置分内部排序：待排序记录存放在计算机随机存储器中（内存）进行的排序过程。外部排序：待排序记录数量很大，内存无法一次容纳全部记录，在排序过程

2、中尚需对外存进行访问的排序过程。15.1排序的基本概念排序分类按照排序依据的原则分插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序15.1排序的基本概念排序分类按排序所需工作量简单的排序方法先进的排序方法基数排序排序基本操作比较两个关键字大小。将记录从一个位置移动到另一个位置。15.1排序的基本概念评价排序的性能——稳定性稳定的排序方法：设在排序前的序列中记录Ri领先于Rj（即i

3、用方法是稳定的。不稳定的排序方法：排序后的序列中Rj领先于Ri。15.1排序的基本概念待排序列：49,38,65,97,76,13,27,49排序后:13,27,38,49,49,65,76,97—稳定排序后:13,27,38,49,49,65,76,97—不稳定插入排序法的基本思想假设：已经存在一个长度为N的有序(从小到大排列)的数据序列，要将一个新的数插入到该序列中，要求插入后的新序列(长度为N+1)仍然保持有序。算法的关键是要确定新数据插入的合适位置。对于一个有序序列，从后向前进行比较，若序列中的数大于要插入的数，则将数列中的数向后移动；否则，完成插入操作。1

4、5.2插入排序—直接插入排序假设待排序的n个记录{R0,R1,…,Rn-1}存放在数组中，插入记录Ri时，记录集合被划分为两个区间[R0，Ri-1]和[Ri，Rn-1]，其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将排序码Ki与Ki-1，Ki-2，…，K0依次比较，找出应该插入的位置，将记录Ri插入，原位置的记录向后顺移。15.2插入排序—直接插入排序i(0)(1)(2)(3)(4)(5)temp[21]254925*1608251[2125]4925*1608492[212549]25*160825*3[212525*49]1608164[162

5、12525*49]08085[0816212525*49]15.2插入排序—直接插入排序基本思想：用折半查找方法确定插入位置的排序。15.2插入排序—折半插入排序例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…i=820(6133039427085)20sjmi=820(6133039427085)20i=820(6133039427085)20i=820(6133039427085)20i=820(613203039427085)sjmjsmsj希尔排序基本思想：将整个待排记录序列分

6、割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。子序列的构成不是简单的“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。具体实现办法先取一个正整数d1

7、327495504493865977613553876270465494997二趟排序结果：13044938274955659776三趟排序结果:04132738494955657697在上例中，第一趟排序时的增量为5，第二趟排序时的增量为3，第三趟排序时的增量为1。由于在前两趟的插入排序中，记录的关键字是与同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录不是一步一步的往前挪动，而是跳跃式的往前移。在进行最后一趟增量为1的插入排序时，序列已基本有序，只要作记录的少量比较和移动即可完成排序。因此比直接插入排序快。希尔排序算法是不稳定的排序算法。15.