CHAPTER排序实用PPT课件

1、2021-10-22110.1 概述1. 什么是排序？ 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97一般情况下，假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 kP(1) kP(2) kP(n) 递增关系或 kP(1) kP(2) kP(n) 递减关系按此

2、固有关系将式(1)的记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。第1页/共58页2021-10-22210.1 概述2.稳定排序和不稳定排序 设文件f=（R1RiRjRn）中记录Ri、Rj（ij，i、j=1n）的key相等，即Ki=Kj。若在排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称这种排序是稳定的，其含义是它没有破坏原本已有序的次序。反之，若排序后Ri与Rj的次序有可能颠倒，则这种排序是不稳定的，即它有可能破坏了原本已有序记录的次序。 3. 内部排序和外部排序 若待排文件f在计算机的内存储器中，且排序过程也在内存中进行，称这种排序为内排序。内排序速度快，但由于内

3、存容量一般很小，文件的长度（记录个数）n受到一定限制。若排序中的文件存入外存储器，排序过程借助于内外存数据交换（或归并）来完成，则称这种排序为外排序。我们重点讨论内排序的一些方法、算法以及时间复杂度的分析。第2页/共58页2021-10-22310.1 概述4. 内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。 使有序区中记录的数目增加一个或几个的操作称为一趟排序。逐步扩大记录有序序列长度的方法大致有下列几类：(1). 插入类 将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长

4、度；(2). 交换类 通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;第3页/共58页2021-10-22410.1 概述(3). 选择类 从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;(4). 归并类 通过“归并”两个或两个以上的记录为有序子序列，逐步增加记录有序序列的长度;(5). 其它方法 5. 文件存储结构（1）顺序结构 类似线性表的顺序存储，将文件纪录存于一片连续的存储空间，逻辑上相邻的记录在存储器中的物理位置也是相邻的。第4页/共58页2

5、021-10-22510.1 概述 在这种结构上对文件排序，一般要作记录的移动。当发生成片记录移动时，是一个很耗时的工作。（2）链表结构 类似于线性表的链式存储，文件中记录用结点来表示，其物理位置任意，结点之间用指针相连，如图： 链表结构的优点在于排序时无须移动记录，只需修改相应记录的指针即可。R1R2RiRn R1 Rn L 第5页/共58页2021-10-22610.1 概述（3）地址映象结构 该结构是另设一地址向量，存储文件中各记录的地址(或序号)，如图： R1 Ri RjRn i j（地址向量地址向量） 排序可在地址向量上进行，一定程度上免去了排序时记录的移动。排序可在地址向量上进行，

6、一定程度上免去了排序时记录的移动。 第6页/共58页2021-10-22710.2 插入排序 假设在排序过程中，记录序列R1.n的状态为： 则一趟直接插入排序的基本思想为：将记录Ri插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i。显然，完成这个“插入”需分三步进行：1查找Ri的插入位置j+1；2将R j+1.i-1中的记录后移一个位置；3将Ri复制到R j+1的位置上。有序子序列有序子序列R1.i-1Ri无序子序列无序子序列Ri+1.n第7页/共58页2021-10-22810.2 插入排序 直接插入排序一. 直接插入排序1.排序方法 先将文件中的（R1）看成只含一

7、个记录的有序子文件，然后从R2起，逐个将R2至Rn按key插入到当前有序子文件中，最后得到一个有序的文件。插入的过程上是一个key的比较过程，即每插入一个记录时，将其key与当前有序子表中的key进行比较，找到待插入记录的位置后，将其插入即可。例 ：设文件记录的key集合k=50，36，66，76，95，12，25，36（考虑到对记录次key排序的情况，允许多个key相同。如此例中有2个key为36，后一个表示成36，以示区别），按直接插入排序方法对k的排序过程如下： 第8页/共58页2021-10-22910.2 插入排序 直接插入排序k=50，36，66，76，95，12，25，3650

8、3636, 50 6636, 50, 66 7636, 50, 66, 76 9536, 50, 66, 76, 95 1212, 36, 50, 66, 76, 95 2512, 25, 36, 50, 66, 76, 95 3612, 25, 36, 36, 50, 66, 76, 95 第9页/共58页2021-10-221010.2 插入排序 直接插入排序2.算法描述void InsertSort ( SqList &L ) /对顺序表L作直接插入排序。 for ( i = 2; i = L.length; +i ) if ( LT( L.ri.key, L.ri1.key ) ) /

9、需将L.ri插入有序子表 L.r0 = L.ri; /复制为哨兵 L.ri = L.ri1; for ( j = i 2; LT( L.r0.key, L.rj.key ); j ) L.rj+1 = L.rj; /记录后移 L.rj+1 = L.r0; /插入到正确位置 / InsertSort第10页/共58页2021-10-221110.2 插入排序 折半插入排序3.算法分析 排序算法一般包括key的比较和记录的移动两种操作，所以算法分析应求出这两种操作的时耗作为算法的时间复杂度。 逆序时耗时最高,因而T(n)=O(n2)。直接插入排序稳定排序。二、折半插入排序 因为R1.i-1是一个按

10、关键字有序的有序序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。 折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。第11页/共58页2021-10-221210.2 插入排序 折半插入排序void BinsertSort ( SqList &L ) /对顺序表L作折半插入排序。 for ( i = 2; i = L.length; +i ) L.r0 = L.ri; /将L.ri暂存到L.r0 low = 1; high = i 1; while ( low = high + 1; j ) L.rj

11、+1 = L.rj; /记录后移 L.rhigh + 1 = L.r0; /插入 / for / BinsertSort第12页/共58页2021-10-221310.2 插入排序 表插入排序三、表插入排序 为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。第13页/共58页2021-10-221410.2 插入排序 希尔排序四、希尔排序（又称缩小增量排序） 基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。 所谓“宏观”调整，指的是，“

12、跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序。关键是，这种子序列不是由相邻的记录构成的。 它的作法不是每次一个元素挨一个元素的比较, 而是初期选用大跨步（增量较大）间隔比较,使记录跳跃式接近它的排序位置; 然后增量缩小; 最后增量为 1, 这样记录移动次数大大减少, 提高了排序效率。希尔排序对增量序列的选择没有严格规定。 第14页/共58页2021-10-221510.2 插入排序 希尔排序第15页/共58页2021-10-221610.2 插入排序 希尔排序void ShellInsert ( Elem R , int dk ) / 对待排序列R作一趟希尔插入

13、排序。本算法对直接插入算法作了以下/ 修改：1. 前后记录位置的增量是dk，而不是1；/ 2. r0只是暂存单元，不是哨兵。当j=0时，插入位置已找到。for ( i=dk+1; i=n; +i ) if ( Ri.key0 & (R0.key Rj.key); j-=dk) Rj+dk = Rj; / 记录后移，查找插入位置 Rj+dk = R0; / 插入 / ShellInsert第16页/共58页2021-10-221710.2 插入排序 希尔排序void ShellSort (Elem R , int dlta , int t) / 按增量序列dlta0.t-1对顺序表L作希尔排序。

14、for (k=0; k=2;i-) 最多n1趟排序 flag=0; for (j=1;jL.Rj+1.key) 两两比较 temp=L.Rj; Rj Rj+1 L.Rj=L.Rj+1; L.Rj+1=temp; flag=1; if (flag=0) break; 无记录交换时排序完毕 第20页/共58页2021-10-222110.3 快速排序 基本思想二、快速排序 快速排序是对起泡排序的一种改进，目的是提高排序的效率。 快速排序又称作分区交换排序。快速排序算法的基本思想是：从待排序的对象数组中任取一个对象（通常是取对象数组中的第一个对象）作基准，调整对象数组中各个对象在数组中的位置，使排在

15、该对象前面的对象的关键字均小于该对象的关键字，使排在该对象后面的对象的关键字均大于等于该对象的关键字。这样的交换过程结束后，将该对象放在了未来排好序的对象数组中该对象应在的位置上；对于左右两个子对象数组中的对象分别再进行方法类同的快速排序，当各个子对象数组中的对象个数均为1时，排序过程结束。 显然，快速排序算法过程是递归的过程。第21页/共58页2021-10-222210.3 快速排序 算法思路 目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列Rs.t将分割成两部分：Rs.

16、i-1和Ri+1.t,且 R j.key Ri.key R j.key (sji-1) 枢轴 (i+1jt)第22页/共58页2021-10-222310.3 快速排序 快排实例k= 50 36 66 76 36 12 25 95 X(枢轴枢轴)ijj25ii66j12i76j36i 25 36 12 36 50 76 66 95 iXjj12i36j 12 25 36 36 jiXj36 36 ijXj66i 66 76 95 排排序序完完毕毕 第23页/共58页2021-10-222410.3 快速排序 算法描述int Partition ( SqList &L, int low, int

17、 high ) /交换顺序表L中子表L.rlow.high的记录，枢轴记录到位，并返/回其所在位置，此时在它之前（后）的记录均不大（小）于它 L.r0 = L.rlow; /用子表的第一个记录作枢轴记录 pivotkey = L.rlow.key; /枢轴记录关键字 while ( low high ) /从表的两端交替地向中间扫描 while ( low = pivotkey ) high; L.rlow = L.rhigh; /将比枢轴记录小的记录移到低端 while ( low high & L.rlow.key = pivotkey ) + + low; L.rhigh = L.rlo

18、w; /将比枢轴记录大的记录移到高端 L.rlow = L.r0; /枢轴记录到位 return low; /返回枢轴位置 / Partition第24页/共58页2021-10-222510.3 快速排序 算法描述void QSort ( SqList &L, int low, int high ) /对顺序表L中的子序列L.rlow.high作快速排序 if ( low high ) /长度大于1 pivotloc = Partition ( L, low, high ); /将L.rlow.high一分为二 QSort ( L, low, pivotloc 1 ); /对低子表递归排序，

19、pivotloc是枢轴位置 QSort ( L, pivotloc + 1, high ); /对高子表递归排序 / QSort第25页/共58页2021-10-222610.3 快速排序 算法分析 快速排序的时间复杂度为 T(n)= O(nlog2n) O(nlog2n)是目前效率最高的内排序时间复杂度。但这是假定每次调用Partition ( )后将原表分成长度相等的两个子表时的情况。若文件F原本就有序（正序或逆序），每次调用一次Partition( )后，文件记录数只减少了一个，故此时T(n)=O(n2)。这是快速排序效率最差的情况。在原文件记录关键字无序时的多种排序方法中, 快速排序被

20、认为是最好的一种排序方法。 第26页/共58页2021-10-222710.4 选择排序 选择排序（Selection Sort）是最符合人们思维习惯的一种排序方法。基本思路是每次从待排文件中挑选一个key值最小的（或最大的）记录放置于它应所在的位置。选择排序一般又分为“简单选择排序”，“树形选择排序”和“堆选择排序”。一、简单选择排序假设排序过程中，待排记录序列的状态为： 并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟简单选择排序是，从无序序列Ri.n的n-i+1记录中选出关键字最小的记录加入有序序列。有序子序列有序子序列R1. i-1无序子序列无序子序列Ri.n第27

21、页/共58页2021-10-222810.4 选择排序 简单选择排序 ij 12 36 66 76 36 50 12 36 36 76 66 50 ij 12 36 36 50 66 76 ij 12 36 36 50 66 76 排序完毕排序完毕k= 50 36 66 76 36 12 ij 12 36 66 76 36 50 i j第28页/共58页2021-10-222910.4 选择排序 简单选择排序void Selectsort (SqList L) 对顺序文件简单选择排序的算法 for (i=1;iL.length;i+) 选择n1趟 j=i; j为本趟最小key的序号 for (

22、k=i+1;k=L.length;k+) 本趟选择 if (L.Rk.keyL.Rj.key) j=k; if (i!=j) L.Ri L.Rj 3.算法分析 设排序文件的记录长度为n。算法中共进行了n1趟选择，每选择一个当前最小key的记录，要经过ni（1in1）次的key比较，时间复杂度T(n)=O(n2)。直接选择排序属于不稳定排序。第29页/共58页2021-10-223010.4 选择排序 树形选择排序 二. 树形选择排序 树形选择排序，又称锦标赛排序（Tournament Sort）,是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在其中 n/2

23、个较小者之间再进行两两比较，如此反复，直至选出最小关键字的记录为止。这个过程可用一棵有n个叶子结点的完全二叉树表示。 第30页/共58页2021-10-223110.4 选择排序 堆排序三. 堆排序 堆排序是J.Willioms于1964年提出的一种排序效率较高、属于选择排序的方法。1.堆定义 设文件F=（R1 R2Rn）的key集合k=k1 k2kn，当且仅当满足：kik2i ki k2ikik2i+1 ki k2i+1 i=1，2n/2 时，称k为堆（或称文件F为堆）。 若将此K序列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时

24、，根结点的值小于(或大于)左/右子树根结点的值。 由此，若上述序列是堆，则K1必是序列中的最小值或最大值，分别称作小顶堆或大顶堆。或第31页/共58页2021-10-223210.4 选择排序 堆排序例： 大顶堆、小顶堆的例子。设k1=95，76，66，50，36，12，25，36，k2=12，36，25，76，36，66，50，95，相应堆如图:95766650361225361236257636665095大顶堆大顶堆小顶堆小顶堆第32页/共58页2021-10-223310.4 选择排序 堆排序 利用堆的特性进行的排序方法即为堆排序，其排序过程如下：假设待排关键字序列为： 34, 39,

25、 20, 65, 47, 12, 98, 73, 81, 56 1）先将它调整为大顶堆： 98, 81, 34, 73, 56, 12, 20, 39, 65, 47 2）互换堆顶和待排序列中 的最后的关键字： 47, 81, 34, 73, 56, 12, 20, 39, 65, 98 3）在待排序列中舍去最大关键字，将其余部 分重新调整为堆： 81, 73, 34, 65, 56, 12, 20, 39, 47 984）重复2）和3）直至待排序列中只剩一个关键字为止。可见，堆排序的两个关键问题是：1） 如何将一个无序序列调整为堆？2）如何在互换堆顶之后重新调整为堆？ 第33页/共58页20

26、21-10-223410.4 选择排序 堆排序 “建堆”过程：若将此序列看成是一个完全二叉树，则最后一个非终端结点是第 n/2 个元素，由此“调整”只需从第 n/2 个元素开始。例：设排序前文件的关键字集合k=50，36，66，76，95，12，25，36建初始堆过程如图：503666951225763612345678953695505076第34页/共58页2021-10-223510.4 选择排序 堆排序2.排序方法 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前n-

27、1记录进行“筛选”，重新调整为一个“大顶堆”，再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。 所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。第35页/共58页2021-10-223610.4 选择排序 堆排序例：对大顶堆k1=95，76，66，50，36，12，25，36排序过程如图：95766636122550363676663612255095507636255066361276369525661225366676369550365012第36页/共58页2021-10-223710.4 选择排序 堆排序36255066761295361

28、225506676369536361225365066763695121236506676369525结果：结果：k1= 12，25，36，36，50，66，76，95 第37页/共58页2021-10-223810.4 选择排序 堆排序void HeapAdjust ( HeapType &H, int s, int m ) /已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，/本函数调整H.rs的关键字，使H.rs.m成为一个大顶堆rc = H.rs;for ( j = 2*s; j = m; j * = 2 ) /沿key较大的孩子结点向下筛选 if ( j 0; i

29、) /把H.r1.H.length建成大顶堆 HeapAdjust ( H, i, H.length ); for ( i = H.length; i 1; i ) H.r1H.ri; /将堆顶记录和当前未经排序子序列Hr1.i中 /最后一个记录相互交换 HeapAdjust ( H, 1, i 1 ); /将H.r1.i 1重新调整为大顶堆 / HeapSort第39页/共58页2021-10-224010.4 选择排序 堆排序3.算法分析)log(2nnO=堆排序的堆排序的时间复杂度时间复杂度：T(n)是一种效率较高的内排序方法。另外，堆排序是不稳定排序。第40页/共58页2021-10-

30、224110.5 归并排序 归并排序（Merging Sort）是采用合并的方法对文件进行排序，这也是外排序经常采用的方法。“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。 我们讨论2-路归并排序。即：将两个位置相邻的有序子序列归并成一个有序序列。1. 排序方法 设待排文件F=（R1 R2Rn），先将每个Ri（1in）看作一个子文件，然后通过key的比较两两归并，得到 n/2 个长度为2的有序子文件，再两两归并，直到得到一个长度为n的有序文件为止。在归并过程中，需要设置一个辅助文件F1。开始时，F为源文件，F1为目标文件，将F归并到F1；然后又将F1作为源文件，F作为目标文件，再

31、将F1归并到F，如此反复，最终排序结果仍在F中。第41页/共58页2021-10-224210.5 归并排序例： 设文件F的记录key集合k=50，36，66，76，95，12，25，36，对F进行二路归并排序的过程如下：F：（：（50 36 66 76 95 12 25 36）F1： 50 36 66 76 95 12 25 36 F： 36 50 66 76 12 95 25 36 F1： 36 50 66 76 12 25 36 95 F： 12 25 36 36 50 66 76 95 完毕完毕第42页/共58页2021-10-224310.5 归并排序2. 算法分析 容易看出，对n个

32、记录进行归并排序的时间复杂度为(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行logn趟。 归并排序属于稳定排序。第43页/共58页2021-10-224410.6 基数排序借助“多关键字排序”的思想来实现“单关键字排序”的算法。一、多关键字的排序 假设有n个记录的序列 R1, R2, ，Rn 每个记录Ri中含有d个关键字(Ki0, Ki1, ,Kid-1),则称上述记录序列对关键字(Ki0, Ki1, ,Kid-1)有序是指：对于序列中任意两个记录Ri和Rj(1ijn)都满足下列(词典)有序关系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1),其

33、中K0被称为“最主”位关键字，Kd-1被称为 “最次”位关键字。第44页/共58页2021-10-224510.6 基数排序实现多关键字排序通常有两种作法:最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，依次类推，直至最后对最次位关键字排序完成为止。最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。第45页/共58页2021-10-224610.6 基数排序例如: 学生记录含

34、三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:无序序列无序序列3,2,301,2,153,1,202,3,182,1,20对对K2排序排序1,2,152,3,183,1,202,1,203,2,30对对K1排序排序3,1,202,1,201,2,153,2,302,3,18对对K0排序排序1,2,152,1,202,3,183,1,203,2,30第46页/共58页2021-10-224710.6 基数排序二、链式基数排序 假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间

35、的比较。 对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。第47页/共58页2021-10-224810.6 基数排序 在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：1.待排序记录以指针相链，构成一个链表； 2.“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同； 3.“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表; 4.对每个关键字位均重复2)和3)两步。 第48页/共58页2021-10-224910.6 基数排序基数排序的时间复杂度为O(d(n+rd)。其中，分配为O(n);收集为O(rd); (rd为“基”)d为“分配-收集”的趟数。第49页/共