排序(网络版)(精品).ppt
《排序(网络版)(精品).ppt》由会员分享,可在线阅读,更多相关《排序(网络版)(精品).ppt(32页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1排序的基本概念排序的基本概念插入排序插入排序快速排序快速排序选择排序选择排序归并排序归并排序基数排序基数排序主要内容主要内容n排序:排序:将一个数据元素(记录)的任意序列,将一个数据元素(记录)的任意序列,重新排列成一个按关键字有序的序列。重新排列成一个按关键字有序的序列。设:设:R1,R2,R3,Rn 是是n个记录,个记录,k1,k2,k3,kn 为它们的关键字,排序就为它们的关键字,排序就是将记录按关键字递增(或递减)的次序排是将记录按关键字递增(或递减)的次序排列起来。列起来。n常见的排序结果常见的排序结果n 递递 增:增:k ki i k ki i+1+1n 非递减:非递减:k ki
2、 i k ki i+1+1n 非递增:非递增:k ki i k ki i+1+115.1 排序的基本概念排序的基本概念n排序分类排序分类n按照排序记录所在的位置分按照排序记录所在的位置分n内部排序:内部排序:待排序记录存放在计算机随机存待排序记录存放在计算机随机存储器中(内存)进行的排序过程。储器中(内存)进行的排序过程。n外部排序:外部排序:待排序记录数量很大,内存无法待排序记录数量很大,内存无法一次容纳全部记录,在排序过程中尚需对外存一次容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。进行访问的排序过程。15.1 排序的基本概念排序的基本概念n排序分类排序分类n按照排序依据的原则分
3、按照排序依据的原则分n插入排序插入排序:直接插入排序、折半插入排序、:直接插入排序、折半插入排序、希尔排序希尔排序n交换排序交换排序:冒泡排序、快速排序:冒泡排序、快速排序n选择排序选择排序:简单选择排序、:简单选择排序、堆排序堆排序n归并排序归并排序:2-路归并排序路归并排序n基数排序基数排序15.1 排序的基本概念排序的基本概念n排序分类排序分类n按排序所需工作量按排序所需工作量n简单的排序方法简单的排序方法n先进的排序方法先进的排序方法n基数排序基数排序n排序基本操作排序基本操作n比较两个关键字大小。比较两个关键字大小。n将记录从一个位置移动到另一个位置。将记录从一个位置移动到另一个位置
4、。15.1 排序的基本概念排序的基本概念n评价排序的性能评价排序的性能稳定性稳定性n稳定的排序方法:稳定的排序方法:设在排序前的序列中记录设在排序前的序列中记录 Ri 领领先于先于 Rj(即(即 ij),且),且 Ri、Rj 对应的关键字为对应的关键字为 Ki、Kj,如果,如果 KiKj 并且在排序后的序列中并且在排序后的序列中 Ri 仍领先仍领先于于 Rj,称所用方法是稳定的。,称所用方法是稳定的。n不稳定的排序方法:不稳定的排序方法:排序后的序列中排序后的序列中Rj领先于领先于Ri。15.1 排序的基本概念排序的基本概念待排序列:待排序列:49,38,65,97,76,13,27,49 排
5、序后排序后:13,27,38,49,49,65,76,97 稳定稳定排序后排序后:13,27,38,49,49,65,76,97不稳定不稳定n插入排序法的基本思想插入排序法的基本思想假假设设:已已经经存存在在一一个个长长度度为为N N的的有有序序(从从小小到到大大排排列列)的的数数据据序序列列,要要将将一一个个新新的的数数插插入入到到该该序序列列中中,要要求求插插入入后后的的新新序序列列(长长度度为为N+1)N+1)仍然保持仍然保持有序有序。算算法法的的关关键键是是要要确确定定新新数数据据插插入入的的合合适适位位置。置。对对于于一一个个有有序序序序列列,从从后后向向前前进进行行比比较较,若若序
6、序列列中中的的数数大大于于要要插插入入的的数数,则则将将数数列列中中的的数向后移动;数向后移动;否则否则,完成插入操作。,完成插入操作。15.2 插入排序插入排序直接插入排序直接插入排序 假设待排序的假设待排序的n n个记录个记录 R R0 0,R,R1 1,R Rn n-1-1 存放存放在数组中,插入记录在数组中,插入记录R Ri i时,记录集合被划分为时,记录集合被划分为两个区间两个区间 R R0 0,R Ri i-1-1 和和 R Ri i,R Rn n-1-1 ,其中,前一其中,前一个子区间已经排好序,后一个子区间是当前未个子区间已经排好序,后一个子区间是当前未排序的部分,将排序码排序
7、的部分,将排序码K Ki i与与K Ki i-1-1,K Ki i-2-2,K K0 0依依次比较,找出应该插入的位置,将记录次比较,找出应该插入的位置,将记录R Ri i插入,插入,原位置的记录向后顺移。原位置的记录向后顺移。15.2 插入排序插入排序直接插入排序直接插入排序i (0)(1)(2)(3)(4)(5)temp 21 25 49 25*16 08 251 21 25 49 25*16 08 492 21 25 49 25*16 08 25*3 21 25 25*49 16 08 164 16 21 25 25*49 08 08 5 08 16 21 25 25*49 15.2 插
8、入排序插入排序直接插入排序直接插入排序基本思想基本思想:用折半查找方法确定插入位置的排序。:用折半查找方法确定插入位置的排序。15.2 插入排序插入排序折半插入排序折半插入排序例例i=1 (30)13 70 85 39 42 6 20i=2 13 (13 30)70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85)20i=8 20 (6 13 30 39 42 70 85)20sjmi=8 20 (6 13 30 39 42 70 85)20i=8 20 (6 13 30 39 42 70 85)20i=8 20 (6 13 30 39 42 70 85)20i
9、=8 20 (6 13 20 30 39 42 70 85)sjmjsmsjn希尔排序基本思想希尔排序基本思想:将整个待排记录序列分割:将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整成为若干子序列分别进行直接插入排序,待整个序列中的记录个序列中的记录“基本有序基本有序”时,再对全体记时,再对全体记录进行一次直接插入排序。录进行一次直接插入排序。子序列的构成不是简单的子序列的构成不是简单的“逐段分割逐段分割”,而是将相隔某个而是将相隔某个“增量增量”的记录组成一个子序的记录组成一个子序列。列。n具体实现办法具体实现办法先取一个正整数先取一个正整数 d1n,把所有相隔把所有相隔d1
10、的的记录放一组,组内进行直接插入排序;记录放一组,组内进行直接插入排序;然后然后取取 d2r2.key,则交换;则交换;然后比较第然后比较第2个记录与第个记录与第3个记录;依次类推,个记录;依次类推,直至第直至第 n-1 个记录和第个记录和第 n 个记录比较为止个记录比较为止第第一趟冒泡排序一趟冒泡排序,结果关键字最大的记录被安置在,结果关键字最大的记录被安置在最后一个最后一个(第(第n个)个)记录上记录上。对前对前 n-1 个记录进行个记录进行第二趟冒泡排序第二趟冒泡排序,结果使,结果使关键字次大的记录被安置在第关键字次大的记录被安置在第n-1个记录位置个记录位置。重复上述过程,直到重复上述
11、过程,直到“在一趟排序过程中没有在一趟排序过程中没有进行过交换记录的操作进行过交换记录的操作”为止为止。一般:一般:n个记录最多进行个记录最多进行 n-1 趟冒泡排序。趟冒泡排序。15.3 交换排序交换排序起泡排序起泡排序冒泡排序冒泡排序冒泡冒泡排序法思想:假设排序法思想:假设6 6个整数为个整数为7 7、-3-3、4343、0 0、1 1和和23237-3430123i=0a5a4a3a2a1a07-34302317-34323017-3432301743-3230143437 7-3-323230 01 1437-32301437-32310437-3231043723-310434323
12、237 7-3-31 10 043237-310i=1i=243237-310432371-30434323237 71 1-3-30 0i=3432371-304323710-3434323237 71 10 0-3-3i=44323710-3434323237 71 10 0-3-3比较比较比较比较 a a j j a a j+1j+1 如果如果如果如果成立成立成立成立两元素交换两元素交换两元素交换两元素交换n 基本思想:通过一趟排序将待排记录分割成基本思想:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字另一
13、部分记录的关键字小小。然后分别对这两部。然后分别对这两部分记录继续进行排序,以达到整个序列有序。分记录继续进行排序,以达到整个序列有序。一趟快速排序:首先选取一个记录(通常选取一趟快速排序:首先选取一个记录(通常选取第一个记录)作为第一个记录)作为界点界点,然后将,然后将所有关键字中所有关键字中比它小的记录比它小的记录都安置在它的位置都安置在它的位置之前之前,将所有,将所有关键字比它大的记录都放在它的位置之后。关键字比它大的记录都放在它的位置之后。由此,以该由此,以该“界点界点”记录最后所落的位置记录最后所落的位置 i 为为分界线分界线,将整个序列分割成,将整个序列分割成两个子序列两个子序列。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序 网络版 精品
限制150内