数据结构ppt课件.ppt

第9章 排序,9.1 排序的基本概念9.2 简单排序方法 9.3 先进排序方法 9.4 各种排序方法的综合比较 9.5 外排序简介,9.1 排序的基本概念,1. 排序,是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。描述如下： 假设含有n个记录的序列为 r1，r2，rn 它们的关键字相应为 k1，k2，kn 使其关键字满足如下非递减（或非递增）关系： 也就是使记录序列重新排列成一个按关键字有序的序列,2. 排序的稳定性 假设Ki=Kj(1in，1jn，ij)， 若在排序前的序列中Ri领先于Rj(即ij)，排序后Ri仍领先于Rj， 称排序方法是稳定的； 若相同关键字的领先关系在排序过程中发生变化，称为不稳定的排序。,证明一种排序方法是稳定的，要从算法本身的步骤中加以证明。 证明排序方法是不稳定的，只需给出一个反例说明,在排序过程中，一般进行两种基本操作： 比较两个关键字的大小； 将记录从一个位置移动到另一个位置。三种常见的存储方法： 向量结构：将待排序的记录存放在一组地址连续的存储单元中。由于在这种存储方式中，记录之间的次序关系由其存储位置来决定，所以排序过程中一定要移动记录才行。 链表结构：采用链表结构时，记录之间逻辑上的相邻性是靠指针来维持的，这样在排序时，就不用移动记录元素，而只需要修改指针。 这种排序方式被称为链表排序。,记录向量与地址向量结合：将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。在排序过程中不移动记录本身，而修改地址向量中的“地址”，排序结束后，再按照地址向量中的值调整记录的存储位置。这种排序方式被称为地址排序。 为了讨论方便，假设待排记录的关键字均为整数，从数组下标为1的位置开始存储，下标为0的位置存储监视哨，或空闲不用。,#define MAXSIZE 20 /*一个用作示例的小顺序表的最大长度*/typedef int KeyType;typedef struct KeyType key; OtherType otherdata; RecordType; typedef struct RecordType rMAXSIZE+1; /*r0闲置或作为判别标志的“哨兵”单元*/ int length; /*顺序表长度*/SqList; /*顺序表类型*/,根据在排序中涉及的存储器不同，将排序方法分为两大类：（1）内部排序：整个排序过程完全在内存中进行。（2）外部排序：由于待排序记录数据量太大，在排序过程中需要对外存进行访问的排序过程。按排序算法的时间复杂度来分，可分为三类：（1）简单的排序方法，其时间复杂度为O（n2）；（2）先进的排序方法，其时间复杂度为O（nlogn）；（3）基数排序，其时间复杂度为O（d*n）。,9.2.1简单选择排序（selection sort） 在简单选择排序的过程中，待排记录序列的状态为：基本思想： 第i趟排序操作：从无序序列Ri.n的n-i+1记录中选出关键字最小的记录Rj和Ri交换，从而使有序序列区从R1.i-1扩大至R1.i，如图9.1所示。,9.2 简单排序方法,常用的有简单选择排序、插入排序和起泡排序。,一趟简单选择排序算法void SelectPass(SqList *L, int i) RecordType temp; j=i; / *j指示关键字最小记录的位置，初值设为i*/ for(k=i+1; klength; k+) if (L-rk.keyrj.key) j=k; /*暂不进行记录交换，只记录位置*/ if (i!=j) /*最后交换记录Rj和Ri*/ temp =L-rj; L-rj=L-ri; L-ri= temp; /*SelectPass,整个选择排序是一趟选择排序过程的多次重复，其算法如下：void SelectSort (SqList *L) /*对顺序表L作简单选择排序*/RecordType temp; for(i=1; ilength; +i) /*选择第i个小的记录，并交换到位*/ j=i; for(k=i+1; klength; k+) /*在L.ri.L.length中选择key最小的记录*/ if(L-rk.keyrj.key) j=k; if (i!=j) temp=L-rj; L-rj=L-ri; L-.ri=temp; /*与第i个记录交换*/ /*SelectSort,例如，对下列一组关键字： （491，38，65，492，76，13，27，52）,算法分析：时间复杂度：移动次数： 最小 0 最大3（n-1）比较次数：n-1, n-2, n-3,1 时间复杂度为O(n2),空间复杂度为O(1),就选择排序方法本身讲，它是一种稳定的排序方法，但图9.2所表现出来的现象是不稳定的，这是由于上述实现选择排序的算法采用的“交换记录”的策略所造成的，若改变这个策略，可以写出不产生“不稳定现象”的选择排序算法。,9.2.2插入排序 1直接插入排序（insertion sort） 基本思想： 在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。 例如：打扑克牌时的抓牌，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。,基本操作： 将当前无序序列区Ri.n中的记录Ri“插入”到有序序列区R1.i-1中，i=2,3,n。使有序序列区的长度增1。,例如：对一组关键字序列49,38,65,492,76,13,27,52进行插入排序过程中，每一趟排序之后的状况如图9.4所示。,假设待排序记录存放在r1.n之中。为了提高效率，附设一个监视哨r0，使得r0 存放待插入的记录。 监视哨作用： 一是备份待插入的记录，以便前面关键字较大的记录后移； 二是防止越界。,void InsertPass(SqList *L, int i) L-r0=L-ri; /*复制为哨兵*/ j=i-1; while (L-r0.key rj.key ) L-rj+1=L-rj; /*记录后移*/ j-; L-rj+1=L-r0 /*插入到正确位置*/ /*InsertPass*/,具体算法描述如下：,整个插入排序需进行n-1趟“插入”。只含一个记录的序列必定是个有序序列，因此插入应从i=2起进行。此外，若第i个记录的关键字不小于第i-1个记录的关键字，“插入”也就不需要进行了。,插入排序的算法如下：void InsertSort (SqList *L) for (i=2; ilength; +i) if (L-ri.keyri-1.key) /*当“r0=L-ri; /*复制为哨兵*/ j=i-1; while (L-r0.key.rj.key) L-rj+1=L-rj; /*记录后移*/ j-; L-rj+1=L-r0; /*插入到正确位置*/ /* if*/ /InsertPass*/,算法性能分析：从空间角度看，需一个辅助空间r0。空间复杂度为S(n)=O(1)。从时间耗费角度看，主要时间耗费在关键字比较和移动元素上。,最好情况：（记录有序） 总的比较次数为n-1次 移动记录的次数也达到最小值2（n-1）最坏情况：（记录逆序） 总的比较次数达到最大值为(n+2)(n-1)/2， 记录移动的次数也达到最大值(n+4)(n-1)/2。,时间复杂度为T(n)=O(n2),直接插入排序是稳定的排序方法。 适用：待排序记录数目较少且基本有序的情况。,2折半插入排序 在有序表中确定插入位置，采用折半查找确定插入位置，即在有序表r1.i-1中用折半查找确定第i个元素的插入位置。,时间复杂度： 比较次数减少了，最大为折半判定树的深度。但移动次数不变。 故为O(n2),void BinSort (RecordType r , int length)/*对记录数组r进行折半插入排序， length为数组的长度*/ for (i=2; i= low; -j ) rj+1= rj; /* 记录依次向后移动 */ rlow=x; /* 插入记录 */ ,3 表插入排序* 直接插入排序、折半插入排序均要大量移动记录，时间开销大。 表插入排序是采用链表存储结构进行插入排序的方法。 基本思想： 先在待插入记录之前的有序子链表中查找应插入位置，然后将待插入记录插入链表。 由于链表的插入操作只修改指针域，不移动记录，所以表插入排序可提高排序效率。 在算法的具体实现上，我们可以采用静态链表作为存储结构。表插入排序示例如图9.5所示。,首先给出类型说明如下：typedef int KeyType;typedef struct KeyType key; OtherType other-data; int next; RecordType1;设r为用RecordType1类型数组表示的静态链表，为了插入方便，用r0做为表头结点，并构成循环链表，即 r0.next指向静态循环链表的第一个结点，rn.next=0。,void SLinkListSort(RecordType1 r, int length) int n=length; r0.next=n; r1.next=0; /*构造只有一个元素的有序静态循环链表*/ for(i=2; i=n-1; -i) p= r0.next; q=0; while(p0 /* 修改指针， 完成插入 */ /* SLinkListSort */ 每插入一条记录，最大的比较次数等于已排好序的记录个数，即当前循环链表长度。所以，总的比较次数为：,4希尔排序（又称缩小增量排序） 较前述直接插入排序方法有较大的改进。,基本思想： 将待排序记录分成若干个子序列，分别进行直接插入排序。 经过上述粗略调整，整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。,希尔排序为一种不稳定的排序方法,希尔排序方法： 选择一个步长序列t1，t2，tk，其中titj，tk=1；ij； 按步长序列个数k，对序列进行k趟排序； 每趟排序，根据对应的步长ti，将待排序列分割成若干子序列，分别对各子表进行直接插入排序。 步长为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。例: 待排序列为 39，80，76，41，13，29，50，78，30，11，100，7，41，86。步长分别取5、3、1，则排序过程如图9.6所示。,void ShellInsert(SqList *L , int delta)/*对L-r 做一趟希尔插入排序， delta 为增量*/for(i=1+delta; ilength; i+) /* 1+delta为第一个子序列的第二个元素的下标 */ if (L-ri.keyri-delta.key) L-r0= L-ri； /* 备份ri (不做监视哨) */ for(j=i-delta；j0&L- r0.key rj.key ；j-=delta) L-rj+delta= L-rj； L-rj+delta= L- r0； void ShellSort( SqList *L)/*对记录数组r做希尔排序*/ for(i=0；i=n-1；+i) ShellInsert(L，deltai)；,9.2.3 冒泡排序思想：两两比较，逆序交换 eg : 49 37 65 27 13 97 76 一趟排序 37 49 27 13 65 76 97,void BubbleSort(SqList *L) /*对记录数组L-r做冒泡排序 */ RecordType temp; n=L-length; change=TRUE； for(i=1; irj.key L-rj+1.key ) temp=L-rj; L-rj=L-rj+1; L-rj+1= temp; change=TRUE； /* BubbleSort */,，,效率度量：最好情况（正序）：需进行一趟排序（即n-1次比较）最坏情况（逆序）： 需进行n-1趟排序（每趟冒泡排序需进行i次比较，3i次移动)。 经过n-1趟冒泡排序后，总的比较次数为(n-i)=n(n-1)/2 总的移动次数为3n(n-1)/2次 该算法的时间复杂度为O(n2)，空间复杂度为O(1)。冒泡排序法是一种稳定的排序方法。,9.3 先进排序方法9.3.1 快速排序 快速排序（quick sort）是从起泡排序改进而得的一种“交换”排序方法。基本思想： 通过一趟排序将记录分割成两部分，一部分记录的关键字均比另一部分记录的关键字小，再分别对两部分排序。（递归）,假设待排序的原始记录序列为（Rs，Rs+1，Rt-1，Rt） 一趟快速排序的基本操作： 任选一个记录（通常选记录Rs），以它的关键字作为“枢轴”，序列中关键字小于枢轴的记录均移动至该记录之前；序列中关键字大于枢轴的记录均移动至该记录之后。,初始关键码： 49 14 38 74 96 65 8 49 55 27,int Partition(RecordType R, int low, int high) R0=Rlow; /*将枢轴记录移至数组的闲置分量*/ Pivotkey=Rlow.key; /*枢轴记录关键字*/ while(low=pivotkey) -high; Rlow+=Rhigh; while(lowhigh /*返回枢轴位置*/ /*Partition,void QSort (RecordType R, int s, int t) /*对记录序列Rs.t进行快速排序*/ if (st-1) /*长度大于1 */ pivotloc=Partition(R,s,t); QSort(R,s,pivotloc-1); QSort(R,pivotloc-1,t); /*对高端子序列递归排序*/ /if/Qsort,性能分析： 分析快速排序的时间耗费, 共需进行多少趟排序，取决于递归调用深度。 最大特点：平均性能很好 最坏情况：单支形式,时间复杂度为O(n2)。 平均性能： O(nlogn),快速排序为一种不稳定的排序方法,9.3.2 归并排序,归并排序法：把两个有序序列归并为一个有序序列。,void Merge(RecordType SR, RcdType TR, int i, int m, int n) /*将有序的SRi.m和SRm+1.n归并为有序的TRi.n */ for(j=m+1,k=i;i=m /*将剩余的SRj.n复制到TR*/Merge,归并排序算法也是一个递归调用的算法，如算法9.13所示。void Msort (RecordType SR, RecordType TR1, int s, int t) if(s=t) TR1s=SRs; else m=(s+t)/2; /*将SRs.t平分为SRs.m和SRm+1.t*/ Msort(SR,TR2,s,m); /*递归地将SRs.m归并为有序的TR2s.m*/ Msort(SR,TR2,m+1,t); /*将SRm+1.t归并为有序的TR2m+1.t*/ Merge(TR2,TR1,s,m,t); /else /Msort,时间复杂度为O(nlogn)，空间复杂度为O(n)。与快速排序相比，归并排序的最大特点是它为一种稳定的排序方法。,9.3.3 堆排序 一. 树形选择排序 树形选择排序也称作锦标赛排序。基本思想： 先把待排序的n个记录的关键字两两进行比较，取出较小的。然后再在个较小的记录中，采用同样的方法进行比较。选出每两个中较小的，如此反复，直到选出最小关键字记录为止。在输出最小记录后，为再次选出次小记录，将根结点即最小记录所对应的叶子结点的关键字的值置为，再进行上述的过程，直到所有的记录全部输出为止。如图9.10所示。,二 堆排序1. 什么是堆? n个元素k1, k2, , kn满足： 或：完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子结点的值。,2堆排序 输出堆顶的最小值之后，将剩余n-1个元素重新建成一个堆，则得n个元素的次小值，反复执行，便能的到一个有序序列。需要解决两个问题： 如何建初始堆； 如何调整为堆。 问题1: 当堆顶元素改变时，如何调整为堆?,问题二：对n个元素初始建堆的过程。建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。 n个结点的完全二叉树，则最后一个结点是第 个结点的孩子结点。对第 个结点为根的子树筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。图9.13给出了“建堆”过程示例。,void sift（RecordType r, int , int ） t=rk ； /* 暂存“根”记录rk */ x=rk.key； i=k； j=2*i； finished=FALSE； while(jrj+1.key) j=j+1；/* 若存在右子树， 且右子树根的关键字大， 则沿右分支“筛选” */ if(x=rj.key) finished=TRUE ； /* 筛选完毕 */ else ri=rj；i=j；j=2*i； /* 继续筛选 */ ri=t ; /* rk填入到恰当的位置 */ /* sift */,建堆算法如下：void crt-heap(RecordType r , int length ) n=length; for(i=n/2; i= 1; -i) /* 自第个记录开始进行筛选建堆 */ sift(r，i，n) ； 堆排序的算法如下： void HeapSort（RecordType r, int length） crt-heap（r, length）； n=length; for ( i=n; i=2; -i) b=r1; /* 将堆顶记录和堆中的最后一个记录互换 */ r1=ri ri=b; sift(r，1，i-1)； /* 进行调整， 使r1.i-1变成堆 */ /* HeapSort */,堆排序在最坏情况下，其时间复杂度也为O(nlog2n)， 这是堆排序的最大优点。堆排序与树形排序相比较，排序中只需要存放一个记录的辅助空间，因此也将堆排序称作原地排序。堆排序是一种不稳定的排序方法。,9.3.4 基数排序* 基数排序（radix sorting）是和前几节讨论的排序方法完全不同的一种排序方法。 从前几节的讨论可见，实现排序主要是通过关键字之间的比较和移动记录这两种操作来完成的; 实现基数排序不需要进行关键字间的比较，而基数排序是一种借助于多关键码排序的思想，是将单关键码按基数分成“多关键码”进行排序的方法。,1. 多关键码排序 例如，可以用分配和收集的方法来对扑克牌进行“排序”。扑克牌中52张牌，按花色和面值分成两个字段，大小关系为： 花色： 梅花方块红心黑桃 面值： 2345678910JQKA,方法1：先对花色排序，再对每个组分别按面值进行排序。 方法2：先按面值给出13个编号组(2号，3号，.，A号)，再按花色给出4个编号组(梅花、方块、红心、黑桃)。 这两种理牌的方法便是两种多关键字的排序方法。,一般情况下，设n个元素的待排序列R1，R2，Rn，且每个记录包含d个关键码k1，k2，kd，则称序列对关键码k1，k2，kd有序是指：对于序列中任两个记录Ri和Rj(1ijn)都满足下列有序关系：,其中k1称为最主位关键码，kd称为最次位关键码,分两种方法 最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD法。 最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法二即是LSD法。,1 链式基数排序,基数排序属于上述“低位优先”排序法，通过反复进行分配与收集操作完成排序。假设记录ri的关键字为keyi，keyi是由d位十进制数字构成的， 即keyi=Ki1 Ki2 Kid， 则每一位可以视为一个子关键字，其中Ki1是最高位，Kid是最低位，每一位的值都在0Kij9的范围内，此时基数rd=10。如果keyi是由d个英文字母构成的， 即keyi=Ki1 Ki2 Kid，其中aKijz， 则基数rd=26。,图9.13 链式基数排序示例,图9.13 链式基数排序示例,图9.13 链式基数排序示例,