华师本科生数据结构课件 第3章 排序.ppt
《华师本科生数据结构课件 第3章 排序.ppt》由会员分享,可在线阅读,更多相关《华师本科生数据结构课件 第3章 排序.ppt(71页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第三章 排序,学习的意义:,早期的计算机约有一半的时间花在排序操作上,虽然随着计算机速度的提高,排序操作不再像早期那样占用计算机过多的时间,但它仍然是信息处理中最常用,也是最重要的运算之一。 实际上,在计算机科学中,排序仍然是组织数据最基本的运算,许多程序和软件均以它作为一个中间步骤。因此,人们设计了大量的排序算法以满足不同的需求。 计算机图灵奖获得者,著名计算机科学家D.E.Knuth在他的巨著Art of Computer Programming中列举分析了25中经典排序方法,并且指出,这只是现有方法中的“一小部分”。,3.1 排序的基本概念 3.2 简单的排序方法 3.2.1 插入排序
2、3.2.2 起泡排序 3.3 先进的排序方法 3.3.1 快速排序 3.3.2 归并排序 3.3.3 堆排序 3.4 基数排序 3.4 各种排序方法的综合比较,主要内容:,在很多情况下,相对于无序表而言,使用有序表可以提高算法效率,因为有序表可以充分利用其有序性采用一些效率较高的算法,例如,在进行数据元素的查找时,采用有序表比无序表效率要高很多。 如何得到有序表?我们可以在构造顺序表的时候依顺序表的有序性进行数据元素的插入,从而求得有序表。 更多的时候,我们需要对一个无序的顺序表进行“排序”,将它转化为“有序”的顺序表。,3. 1 排序的基本概念,排序 是按关键字的非递减或非递增顺序对一组记录
3、重新进行整队(或)排列的操作.,姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 .,3. 1 排序的基本概念,例1、高考考生信息管理系统提供了将考生按总分排序、按单科排序的功能; 例2、数学中的数列(11,13,15,17,19,21)例3、英文字母表(A, B, C, D, E Z )。例4、某单位的电话号码簿。,排序的定义,排序的形式化描述,假设含有n个记录的序列为: r1,r2,r3,rn 它们的关键字相应为: k1,k2,k3,kn 对记录序列进行排序就是确定序号1,2,3,n的一种排列: p1
4、,p2,p3,pn 使其相应的关键字满足非递减或非递增的关系 kp1 kp2 kp3。 kpn 也就是使记录序列重新排列成为一个按关键字有序的序列,排序分类,什么叫内部排序?什么叫外部排序?,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序;称为内部排序; 反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。,注:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多。,内部排序的算法有哪些?,按排序的规则不同,可分为5类: 插入排序 交换排序(重点是快速排序) 选择排序 归并排序 基数排序,d关键
5、字的位数(长度),按排序算法的时间复杂度不同,可分为3类: 简单的排序算法:时间效率低,O(n2) 先进的排序算法: 时间效率高,O( nlog2n ) 基数排序算算法:时间效率高,O( dn),按稳定性分类: 在待排记录序列中,任何两个关键字相同的记录,用某种排序方法排序后相对位置不变,则称这种排序方法是稳定的,否则称为不稳定的。 例 设 49,38,65,97,76,13,27,49 是待排序列 排序后:13,27,38,49,49,65,76,97 稳定 排序后:13,27,38,49,49,65,76,97不稳定 稳性排序的应用: 例 股票交易系统 考虑一种股票交易(清华紫光)) 1)
6、顾客输入:股东帐号、股票代码、申购价格、数量,股票交易系统将用户申购请求插入申购队列队尾; 2)股票交易系统按如下原则交易: A)申购价高者先成交 B)申购价相同者按申购时间先后顺序成交,如何实现股票交易系统 ?申购队列:用线性表表示 交易前:将申购队列按申购价排序,显然为满足原则交易B),要求排序方法是稳定的 申购队列(09,10),(06,10.5),(033,9.8),(051,10) 排序后:(06,10.5),(09,10),(051,10),(033,9.8),待排序记录在内存中怎样存储和处理?, 顺序排序排序时直接移动记录; 链表排序排序时只移动指针; 地址排序排序时先移动地址,
7、最后再移动记录。,注:地址排序中可以增设一维数组来专门存放记录的地址。,内部排序的方法,内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,选择排序,从记录的无序子序列中“选择”关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。,【算法3.1 】一趟选择排序的算法如下: void SelectPass( SqList k+ ) if ( L.rk.key L.rj.key ) j = k ; / 暂不进行记录交换,只记录位置 if ( i != j ) W=L.rj;L.rj
8、 =L.ri;L.ri = W; / 最后互换记录Rj 和Ri / SelectPass,【算法3.2 】 void SelectSort (SqList k+ ) / 在L.ri.L.length中选择key最小的记录 if ( L.rk.key L.rj.key ) j =k ; if ( i!=j ) W=L.rj;L.rj =L.ri;L.ri = W; / 与第i个记录交换 / SelectSort,整个选择排序的过程是一趟选择排序过程的多次重复,融合SelectPass。,初试关键字: 491 38 65 492 76 13 27 52 i=1 (13) 38 65 492 76
9、491 27 52 i=2 (13 27)65 492 76 491 38 52 i=3 (13 27 38) 492 76 491 65 52 i=4 (13 27 38 492)76 491 65 52 i=5 (13 27 38 492 491)76 65 52 i=6 (13 27 38 492 491 52)65 76 i=7 (13 27 38 492 491 52 65 )76,【例3-1 】对下面一组关键字: 491 38 65 492 76 13 27 52 进行选择排序,每趟排序之后的状况如下:,选择排序时间性能分析,对 n 个记录进行简单选择排序,所需进行的 关键字间的比
10、较次数 总计为:,移动记录的次数,最小值为 0, 最大值为3(n-1),简单排序算法,除前面讨论的选择排序外,常用的还有插入排序和起泡排序。,3.2 简单排序方法,插入排序的基本思想: 每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。,简而言之,边插入边排序,保证子序列中随时都是排好序的。,利用 “顺序查找”实现“在R1.i-1中查找Ri的插入位置”,直接插入排序,算法实现: 当插入第i (i 1) 个对象时, 前面的r0, r1, , ri-1已经排好序。这时, 用ri的排序码与ri-1, ri-2, 的排序码顺序进行比较, 找到插入
11、位置即将ri插入, 原来位置上的对象向后顺移。,有序序列R1.i-1,Ri,无序序列 Ri.n,有序序列R1.i,无序序列 Ri+1.n,一趟直接插入排序的基本思想:,【算法3.3 】 void InsertPass( SqList / 插入到正确位置 / InsertPass,注意:“哨兵”的作用,一趟插入排序,从Ri-1起向前进行顺序查找,监视哨设置在R0;,R0 = Ri; / 设置“哨兵”,循环结束表明Ri的插入位置为 j +1,R0,j,Ri,for (j=i-1; R0.keyRj.key; -j); / 从后往前找,插入位置,对于在查找过程中找到的那些关键字不小于Ri.key的记
12、录,并在查找的同时实现记录向后移动;,for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj,R0,j,Ri,j= i-1,上述循环结束后可以直接进行“插入”,插入位置,例2:关键字序列T= (21,25,49,25*,16,08),请写出直接插入排序的具体实现过程。,*表示后一个25,i=1,21,i=2,i=3,i=5,i=4,i=6,25,25,25,49,49,49,25*,49,16,16,08,49,解:假设该序列已存入一维数组V7中,将V0作为缓冲或暂存单元(Temp)。则程序执行过程为:,初态:,16,25,21,16,完成!,时间效率:O(n2)因为
13、在最坏情况下,所有元素的比较次数总和为(01n-1)O(n2)。其他情况下还要加上移动元素的次数。 空间效率:O(1)因为仅占用1个缓冲单元 算法的稳定性:稳定因为25*排序后仍然在25的后面。,【算法3.4 】 void InsertSort ( SqList / 插入到正确位置 / if / InsertSort,整个插入排序需要进行n-1趟“插入”。 因为只含有一个关键字的序列必定是有序序列,因此,插入应该从i=1开始进行,此外,若第i个记录的关键字不小于第i-1个关键字,插入也就不需要进行了。,初始时,有序子表中只有一个元素,待排序记录集合:,i=2 i=3 i=4,L.r0.key
14、L.r4.key, L.r4记录后移,看一下外层For循环 i=5 时算法的执行的情况,L.r5复制为哨兵,L.r0.key L.r3.key 找到插入位置,L.r5为待插入元素,插入!,时间复杂度: 待排序列正向有序时 :0 (n) 待排序列逆向有序时: 0(n2) 一般待排序列:0(n2) 插入排序特点: 1) 算法简单 2) 时间复杂度为O(n2 ) 3)初始序列基本(正向)有序时,时间复杂度为O(n) 4)稳定排序 该方法适用于记录基本(正向)有序或n较少的情况,性能分析:基本操作: 比较元素:比较、移动元素次数均取决于插入位置 移动元素处理第i个记录时 待排序列递增(正向)有序时,比
15、较元素次数最少:1次 待排序列递减(逆向)有序时,比较元素次数最多:i 次 一般待排序列,平均比较元素次数: (i+1)/2 对n个记录待排序列,直接插入排序 待排序列正向有序时,比较元素次数最少:n-1次 待排序列逆向有序时,比较元素次数最多:(n+2)(n-1)/2次 一般待排序列,平均比较元素次数大约为:n2/4 类似可分析移动元素次数,3.2.2 起泡排序,基本思想: 是通过对无序序列区中的记录进行相邻记录关键字的“比较”和记录位置的“交换”实现较小的记录向“一头”漂移,而关键字较大的记录向“另一头”下沉,从而达到记录按关键字非递减有序排列的目标。,假设在排序过程中,记录序列R1.n的
16、状态为:,第 i 趟起泡排序,无序序列R1.n-i+1,有序序列 Rn-i+2.n,n-i+1,无序序列R1.n-i,有序序列 Rn-i+1.n,比较相邻记录,将关键字最大的记录交换到 n-i+1 的位置上,1) 冒泡排序,基本思路:每趟不断将记录两两比较,并按“前小后大”(或“前大后小”)规则交换。 优点:每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素;一旦下趟没有交换发生,还可以提前结束排序。 前提:顺序存储结构,例:关键字序列 T=(21,25,49,25*,16,08),请写出冒泡排序的具体实现过程。,21,25,49, 25*,16, 08 21,25,25*
17、,16, 08 , 49 21,25, 16, 08 ,25*,49 21,16, 08 ,25, 25*,49 16,08 ,21, 25, 25*,49 08,16, 21, 25, 25*,49,初态: 第1趟 第2趟 第3趟 第4趟 第5趟,【具体算法 3.5 】 void BubbleSort( SqList / 一趟排序中无序序列中最后一个记录的位置 / while / BubbleSort 空间复杂度O(1),注意:,2. 一般情况下,每经过一趟“起泡”,“i 减一”,但并不是每趟都如此。,例如:,i=7,for (j = 1; j i; j+) if (Rj+1.key Rj.
18、key) ,1. 起泡排序的结束条件为, 最后一趟没有进行“交换记录”。,2,3,1,5,7,8,9,i=6,i=2,3,1,1,3,时间分析:,最好的情况(关键字在记录序列中顺序有序): 只需进行一趟起泡,“比较”的次数:,最坏的情况(关键字在记录序列中逆序有序): 需进行n-1趟起泡,“比较”的次数:,0,“移动”的次数:,“移动”的次数:,n-1,3.3 先进的排序方法 3.3.1 快速排序(quick sort) 快速排序是从起泡排序改进而得的一种“交换”排序方法,它的基本思想是通过一趟排序将将记录分割成相邻的两个区域,其中一个区域中记录的关键字均比另一区域中记录关键字小(区域内不一定
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 华师本科生数据结构课件 第3章 排序 本科生 数据结构 课件
限制150内