第10章内排序ppt课件.ppt

第10章 内 排 序,10.6 基数排序,10.1 排序的基本概念,10.2 插入排序,10.3 交换排序,10.4 选择排序,10.5 归并排序,10.7 各种内排序方法的比较和选择,10.1 排序的基本概念 所谓排序，是要整理表中的记录，使之按关键字递增（或递减）有序排列。其确切定义如下：输入：n个记录,R0,R1,Rn-1,其相应的关键字分别为k0,k1,kn-1。输出：Ri,0,Ri,1,Ri,n-1,使得ki,0ki,1ki,n-1(或ki,0ki,1ki,n-1)。,本章仅考虑递增排序,当待排序记录的关键字均不相同时，排序的结果是惟一的,否则排序的结果不一定唯一。如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的；反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。,在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。,算法的稳定性,内排序和外排序,内排序的基本方法,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,正序和反序若待排序的表中元素已按关键字排好序，称此表中元素为正序；反之，若待排序的表中元素的关键字顺序正好和排好序的顺序相反，称此表中元素为反序。,排序的分类根据排序算法是否基于关键字的比较，将排序算法分为基于比较的排序算法和不基于比较的排序算法。像插入排序、交换排序、选择排序和归并排序都是基于比较的排序算法；而基数排序是不基于比较的排序算法。,待排序的顺序表类型的类型定义如下：typedef int KeyType;/定义关键字类型 typedef struct/记录类型 KeyType key;/关键字项 InfoType data;/其他数据项,类型为InfoType RecType;/排序的记录类型定义,存放数据的结构：,10.2 插入排序 插入排序的基本思想是：每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。两种插入排序方法：（1）直接插入排序（含二分插入排序）（2）希尔排序,10.2.1 直接插入排序 假设待排序的记录存放在数组R0.n-1中，排序过程的某一中间时刻，R被划分成两个子区间R0.i-1和Ri.n-1，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。直接插入排序的基本操作是将当前无序区的第1个记录Ri插入到有序区R0.i-1中适当的位置上，使R0.i变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。,R0,j,Ri,j=i-1,插入位置,在有序区中插入Ri的过程,void InsertSort(RecType R,int n)/对R0.n-1按递增有序进行直接插入排序 int i,j;RecType temp;for(i=1;i=0/在j+1处插入Ri,例10.1 设待排序的表有10个记录，其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用直接插入排序方法进行排序的过程。,对于直接插入排序：,最好的情况（关键字在记录序列中顺序有序）：,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）：,“比较”的次数：,2(n-1),“移动”的次数：,“移动”的次数：,总的平均比较和移动次数约为,直接插入排序算法稳定性证明：另外，当ij且Ri.key=Rj.key时，本算法将Ri插入在Rj的后面，使Ri和Rj的相对位置保持不变，所以直接插入排序是一种稳定的排序方法。,Rj Ri,有序区,Ri插入在Rj的后面,10.2.2 折半插入排序,查找采用折半查找方法，称为二分插入排序或折半插入排序。void InsertSort1(RecType R,int n)int i,j,low,high,mid;RecType tmp;for(i=1;i=high+1;j-)/记录后移 Rj+1=Rj;Rhigh+1=tmp;/插入,折半插入排序的元素移动次数与直接插入排序相同，不同的仅是变分散移动为集合移动。在R0.i-1中查找插入Ri的位置，折半查找的平均关键字比较次数为log2(i+1)-1，平均移动元素的次数为i/2+2，所以平均时间复杂度为：,就平均性能而言，折半查找优于顺序查找，所以折半插入排序也优于直接插入排序。折半插入排序的空间复杂度为O(1)。,10.2.3 希尔排序 希尔排序也是一种插入排序方法,实际上是一种分组插入方法。基本思想：先取定一个小于n的整数d1作为第一个增量，把表的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2（d1），重复上述的分组和排序，直至所取的增量dt=1（dtdt-1d2d1），即所有记录放在同一组中进行直接插入排序为止。,将记录序列分成若干子序列，分别对每个子序列进行插入排序。,其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。,例如：将 n 个记录分成 d 个子序列：R0，Rd，R2d，Rkd R1，R1+d，R1+2d，R1+kd Rd-1，R2d-1，R3d-1，R(k+1)d-1,例如：,16 25 12 30 47 11 23 36 9 18 31,设增量 d=5:,11 23 12 9 18 16 25 36 30 47 31,void ShellSort(RecType R,int n)/希尔排序算法 int i,j,gap;RecType tmp;gap=n/2;/增量置初值 while(gap0)for(i=gap;i=0/减小增量,例10.2 设待排序的表有10个记录,其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用希尔排序方法进行排序的过程。,希尔排序的时间复杂度约为O(n1.3)。为什么希尔排序比直接插入排序好？例如：有10个元素要排序。,希尔排序,直接插入排序,大约时间=102=100,d=5：分为5组，时间约为5*2220,d=2：分为2组，时间约为2*5250,d=1：分为1组，几乎有序，时间约为10,80,希尔排序算法不稳定的反例希尔排序法是一种不稳定的排序算法。例如，若希尔排序分为两组：3,10,7,8,20和5,8,2,1,6，显然，第1组的8排列在第2组的8的后面，两组采用直接插入排序后的结果为：3,7,8,10,20和1,2,5,6,8，这样第1组的8排列到第2组的8的前面，它们的相对位置发生了改变。,思考题：希尔排序中的有序区是全局有序吗？,10.3 交换排序 交换排序的基本思想：两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。两种交换排序:（1）冒泡排序（2）快速排序,10.3.1 冒泡排序 冒泡排序的基本思想：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。整个算法是从最下面的记录开始，对每两个相邻的关键字进行比较,且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着再在剩下的记录中找关键字次小的记录，并把它换在第二个位置上。依次类推，一直到所有记录都有序为止。,void BubbleSort(RecType R,int n)int i,j;RecType temp;for(i=0;ii;j-)/比较找本趟最小关键字的记录 if(Rj.keyRj-1.key)temp=Rj;/Rj与Rj-1进行交换 Rj=Rj-1;Rj-1=temp;,全局有序区 Ri Rn-1,用交换找最小记录放到Ri处,例10.3 设待排序的表有10个记录,其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用冒泡排序方法进行排序的过程。,思考题：冒泡排序中的有序区是全局有序吗？,在有些情况下，在第i（in-1）趟时已排好序了，但仍执行后面几趟的比较。实际上，一旦算法中某一趟比较时不出现记录交换，说明已排好序了，就可以结束本算法。为此得到改进冒泡排序算法如下：,void BubbleSort(RecType R,int n)int i,j;bool exchange;RecType temp;for(i=0;ii;j-)/比较,找出最小关键字的记录 if(Rj.keyRj-1.key)temp=Rj;Rj=Rj-1;Rj-1=temp;exchange=true;if(exchange=false)return;/中途结束算法,最好的情况（关键字在记录序列中顺序有序）：只需进行一趟冒泡,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟冒泡,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,n-1,10.3.2 快速排序 快速排序是由冒泡排序改进而得的。基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位)，这个过程称作一趟快速排序。,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。,无 序 的 记 录 序 列,无序记录子序列(1),无序子序列(2),基准,一次划分,分别进行快速排序,需要确定排序的序列，采用什么存储结构？,s,t,low,high,设 Rs=52 为枢轴,将 Rhigh.key 和基准的关键字进行比较，要求Rhigh.key 基准的关键字,将 Rlow.key 和基准的关键字进行比较，要求Rlow.key 基准的关键字,high,23,low,80,high,14,low,52,例如,R0,52,low,high,high,high,low,可见，经过“一次划分”，将关键字序列 52,49,80,36,14,58,61,97,23,75 调整为:23,49,14,36,(52)58,61,97,80,75,在调整过程中，设立了两个指针：low 和high，它们的初值分别为：s 和 t。,之后逐渐减小 high，增加 low，并保证 Rhigh.key52，和 Rlow.key52,否则进行记录的“交换”。,以后对所有的两部分分别重复上述过程，直至每部分内只有一个记录为止。简而言之，每趟使表的第一个元素放入适当位置，将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为1。,void QuickSort(RecType R,int s,int t)/对Rs至Rt的元素进行快速排序 int i=s,j=t;RecType temp;if(si/对右区间递归排序,划分,例10.4 设待排序的表有10个记录,其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用快速排序方法进行排序的过程。,则可得结果：,结论:快速排序的时间复杂度为O(nlog2n),由此可得快速排序所需时间的平均值为：,平均所需栈空间为O(log2n)。,n,k-1,n-k,1次划分的时间,Tavg(n)=Cnlog2n。,10.4 选择排序 选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。两种选择排序方法：（1）简单选择排序（或称直接选择排序）（2）堆排序,10.4.1 直接选择排序基本思想：第i趟排序开始时,当前有序区和无序区分别为R0.i-1和Ri.n-1（0in-1），该趟排序则是从当前无序区中选出关键字最小的记录Rk，将它与无序区的第1个记录Ri交换，使R0.i和Ri+1.n-1分别变为新的有序区和新的无序区。,假设排序过程中，待排记录序列的状态为：,有序序列R0.i-1,无序序列 Ri.n-1,第 i 趟简单选择排序,从中选出关键字最小的记录,有序序列R0.i-1,无序序列 Ri+1.n-1,void SelectSort(RecType R,int n)int i,j,k;RecType temp;for(i=0;in-1;i+)/做第i趟排序 k=i;for(j=i+1;jn;j+)/在i.n-1中选key最小的Rk if(Rj.keyRk.key)k=j;/k记下的最小关键字所在的位置if(k!=i)/交换Ri和Rk temp=Ri;Ri=Rk;Rk=temp;,全局有序区 Ri Rn-1,用选择找最小记录放到Ri处,例10.5 设待排序的表有10个记录，其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用直接选择排序方法进行排序的过程。,对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数 总计为：,移动记录的次数，最小值为 0,最大值为3(n-1)。,10.4.2 堆排序 堆排序是一树形选择排序，它的特点是，在排序过程中，将R1.n看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。堆的定义是：n个关键字序列K1,K2,Kn称为堆,当且仅当该序列满足如下性质（简称为堆性质）：（1）KiK2i 且 KiK2i+1 或（2）KiK2i 且 KiK2i+1（1in/2）满足第（1）种情况的堆称为小根堆，满足第（2）种情况的堆称为大根堆。下面讨论的堆是大根堆。,12,36,27,65,40,34,98,81,73,55,49是小根堆,例如:,12,36,27,65,40,14,98,81,73,55,49不是堆,ri,r2i,r2i+1,若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子；r2i+1 是 ri 的右孩子。,12,36,27,65,49,81,73,55,40,34,98,例如:,是堆,14,不,堆排序的关键是构造堆,这里采用筛选算法建堆。所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。,堆,堆,筛选,堆,98,81,49,73,55,64,12,36,27,40,例如:,是大根堆,12,但在 98 和 12 进行互换之后，它就不是堆了，,因此，需要对它进行“筛选”。,98,12,81,73,64,12,98,比较,比较,void sift(RecType R,int low,int high)/调整堆的算法 int i=low,j=2*i;/Rj是Ri的左孩子 RecType temp=Ri;while(j=high)if(jhigh,low,2*low,2*low+1,high,有了调整堆的函数,利用该函数,将已有堆中的根与最后一个叶子交换,进一步恢复堆,直到一棵树只剩一个根为止。实现堆排序的算法如下：,void HeapSort(RecType R,int n)int i;RecType temp;for(i=n/2;i=1;i-)/循环建立初始堆 sift(R,i,n);for(i=n;i=2;i-)/进行n-1次循环,完成推排序 temp=R1;/将第一个元素同当前区间内R1对换 R1=Ri;Ri=temp;sift(R,1,i-1);/筛选R1结点,得到i-1个结点的堆,例10.6 设待排序的表有10个记录，其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用堆排序方法进行排序的过程。,堆排序过程：,堆排序的时间复杂度分析：,1.对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；,3.调整“堆顶”n-1 次，总共进行的关键 字比较的次数不超过 2(log2(n-1)+log2(n-2)+log22)2n(log2n),因此，堆排序的时间复杂度为O(nlogn)。,2.对 n 个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数不超过4n；,思考题：选择排序中的有序区是全局有序吗？,10.5 归并排序 归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。,在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列。,归并为一个记录的有序序列。,有 序 序 列 Rl.n,有序子序列 Rl.m,有序子序列 Rm+1.n,这个操作对顺序表而言，是轻而易举的。,void Merge(RecType R,int low,int mid,int high)RecType*R1;int i=low,j=mid+1,k=0;/k是R1的下标,i、j分别为第1、2段的下标 R1=(RecType*)malloc(high-low+1)*sizeof(RecType);while(i=mid,Merge()实现了一次归并:,空间复杂度为O(high-low+1),while(i=mid)/将第1段余下部分复制到R1 R1k=Ri;i+;k+;while(j=high)/将第2段余下部分复制到R1 R1k=Rj;j+;k+;for(k=0,i=low;i=high;k+,i+)/将R1复制回R中 Ri=R1k;free(R1);,void MergePass(RecType R,int length,int n)int i;for(i=0;i+2*length-1n;i=i+2*length)/归并length长的两相邻子表 Merge(R,i,i+length-1,i+2*length-1);if(i+length-1n)/余下两个子表,后者长度小于length Merge(R,i,i+length-1,n-1);/归并这两个子表,MergePass()实现了一趟归并,二路归并排序算法如下：void MergeSort(RecType R,int n)int length;for(length=1;lengthn;length=2*length)MergePass(R,length,n);,例10.7 设待排序的表有8个记录,其关键字分别为18,2,20,34,12,32,6,16,1,5。说明采用归并排序方法进行排序的过程。,18 2 20 34 12 32 6 16 1 5,初始：,2 18 20 34 12 32 6 16 1 5,2 18 20 34 6 12 16 32 1 5,2 6 12 16 18 20 32 34 1 5,1 2 5 6 12 16 18 20 32 34,log210取上界为4,第1趟,第2趟,第3趟,第4趟,容易看出，对 n 个记录进行归并排序的时间复杂度为(nlogn)。即：每一趟归并的时间复杂度为 O(n)，总共需进行 log2n 趟。,二路归并,多路归并,例如，对任意的7个关键字进行基于比较的排序，至少要进行 次关键字之间的两两比较。A.13B.14 C.15D.16 解：基于“比较”进行排序的算法在最坏情况下所需进行的比较次数至少为log2(n!)。log2(7!)=13。本题答案为A。,例如，若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是。A.起泡排序B.插入排序 C.选择排序 D.二路归并排序,本题为2009年全国考研题,例如，数据序列8,9,10,4,5,6,20,1,2只能是 的两趟排序后的结果。A.简单选择排序B.起泡排序 C.直接插入排序 D.堆排序,例如，已知关键字序列5,8,12,19,28,20,15,22是小根堆，插入关键字3，调整好后得到的小根堆是。A.3,5,12,8,28,20,15,22,19 B.3,5,12,19,20,15,22,8,28 C.3,8,12,5,20,15,22,28,19 D.3,12,5,8,28,20,15,22,19,本题为2009年全国考研题,例如，对一组数据(2,12,16,88,5,10)进行排序，若前三趟的结果如下：第一趟：2,12,16,5,10,88 第二趟：2,12,5,10,16,88 第三趟：2,5,10,12,16,88则采用的排序方法可能是。A.起泡排序B.希尔排序 C.归并排序D.基数排序,本题为2010年全国考研题,例如，采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是。A.递归次数与初始数据的排列次序无关 B.每次划分后，先处理较长的分区可以减少递归次数 C.每次划分后，先处理较短的分区可以减少递归次数 D.递归次数与每次划分后得到的分区处理顺序无关,例如，为实现快速排序法，待排序序列宜采用存储方式是。A.顺序存储B.散列存储 C.链式存储 D.索引存储,本题为2011年全国考研题,本题为2010年全国考研题,10.6 基数排序 前面所讨论的排序算法均是基于关键字之间的比较来实现的，而基数排序是通过“分配”和“收集”过程来实现排序，是一种借助于多关键字排序的思想对单关键字排序的方法。,一般地，记录Ri的关键字Ri.key是由d位数字组成，即kd-1kd-2k0，每一个数字表示关键字的一位，其中kd-1为最高位，k0是最低位，每一位的值都在0kir范围内，其中r称为基数。例如，对于二进制数r为2，对于十进制数r为10。基数排序有两种：最低位优先（LSD）和最高位优先（MSD）。最低位优先的过程是：先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。,以r为基数的最低位优先排序的过程是：假设线性表由结点序列a0,a1,an-l构成，每个结点aj的关键字由d元组（kjd-1,kjd-2,kj1,kj0）组成，其中0kjir-1（0jn，0id-1）。在排序过程中，使用r个队列Q0,Q1,Qr-1。排序过程如下：对i=0,1,d-1，依次做一次“分配”和“收集”（其实就是一次稳定的排序过程）。分配：开始时，把Q0,Q1,Qr-1各个队列置成空队列，然后依次考察线性表中的每一个结点aj（j=0,1,n-1），如果aj的关键字kji=k，就把aj放进Qk队列中。收集：把Q0,Q1,Qr-1各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。,例如：,p369367167239237138230139,进行第一次分配,进行第一次收集,f0 r0,f7 r7,f8 r8,f9 r9,p230,230,367,167,237,367167237,138,368239139,369,239,139,138,进行第二次分配,p230237138239139,p230367167237138368239139,f3 r3,f6 r6,230,237,138,239,139,367,167,368,367167368,进行第二次收集,进行第三次收集之后便得到记录的有序序列,f1 r1,p230237138239139367167368,进行第三次分配,f2 r2,f3 r3,138,139,167,230,237,239,367,368,p138139167,230237239,367368,#define MAXE 20/线性表中最多元素个数#define MAXR 10/基数的最大取值#define MAXD 8/关键字位数的最大取值typedef struct node char dataMAXD;/记录的关键字定义的字符串 struct node*next;RecType1;/单链表中每个结点的类型,a1,p,a2,a3,an,基数排序数据的存储结构,void RadixSort(RecType1*/取下一个待排序的元素,分配,p=NULL;for(j=0;jnext=headj;t=tailj;t-next=NULL;/最后一个结点的next域置NULL,收集,排序完成后，p指向的是一个有序单链表,例10.8 设待排序的表有10个记录，其关键字分别为75,23,98,44,57,12,29,64,38,82。说明采用基数排序方法进行排序的过程。,基数排序的时间复杂度为O(d(n+r),其中：分配为O(n)收集为O(r)（r为“基数”）d为“分配-收集”的趟数,思考题：基数排序的主要特点是什么？,10.7 各种内排序方法的比较和选择 本章介绍了多种排序方法，将这些排序方法总结为表10.1。通常可按平均时间将排序方法分为三类：（1）平方阶O(n2)排序，一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶O(nlog2n)排序，如快速、堆和归并排序；（3）线性阶O(n)排序，如基数排序（假设r、d为常量）。,练习题10,10.2、10.4和10.6,