二级vb公共基础2 排序

《二级vb公共基础2 排序》由会员分享，可在线阅读，更多相关《二级vb公共基础2 排序（39页珍藏版）》请在金锄头文库上搜索。

1、排 序排序是数据处理中经常使用的一种重要运算研究问题:p如何进行排序p如何进行高效率排序1排序的基本概念 q假设条件:u假定排序的对象是由一组记录组成的文 件，记录由若干字段组成，以排序码为 依据排序q排序码-记录中的一个(或多个)字段u关键码-此时按关键码排序、排序的结果唯 一u不是关键码-则可能有多个记录具有相同的 排序码，排序的结果不唯一2q排序:设R0,R1,Rn-1是由n个记录 组成的文件，K0,K1,Kn-1是排序 码集合，排序是将记录按排序码不增( 或不减)的次序排列q排序的稳定与不稳定基本概念3q按排序方法:u插入排序u选择排序u交换排序u分配排序u归并排序 q按排序中涉及的存

2、储器不同:u内排序:待排序的记录在排序过程中全部存放在 内存的u外排序:如果排序过程中需要使用外存的排序的种类4排序的基本操作q比较u比较两个关键字的大小u必须操作q移动u将一个记录从一个位置移动到另一个位置u非必须操作,可通过存储方式来避免(如静 态链表)5q评价排序算法好坏的标准u执行算法所需的时间u执行算法所需要的附加空间u算法本身的复杂程度也是考虑的一个因素q排序的时间开销是算法好坏的最重要的 标志u排序的时间开销衡量标准:算法执行中的比较次数算法执行中的移动次数 排序算法的评价6插入排序q基本方法每步将一个待排序的记录，按其排序 码大小插到前面已经排序的文件中的 适当位置，直到全部插

3、入完为止。q种类：n直接插入排序n二分法插入排序n表插入排序nshell排序7直接插入排序q方法:u假设待排序的n个记录R0,R1,Rn-1存 放在数组中，插入记录Ri时，记录集合被 划分为两个区间R0，Ri-1 和Ri，Rn-1 R0，Ri-1 已经排好序Ri，Rn-1 是当前未排序的部分u将排序码Ki与Ki-1，Ki-2，K0依次比较 ，找出应该插入的位置，将记录Ri插入， 原位置的记录向后顺移u直接插入排序采用顺序存储结构 8直接插入排序的算法初始化 申明temp为记录结点类型j=i-1将关键码比temp大的记录后移 recordj+1=recordj继续向前比较 j-endi0 Yj

4、!= i-1？NY找到插入位置将temp插入 recordj+1=tempAA下标为i的记录位置不变N9二分法插入排序q直接插入排序的算法简洁，容易实现，n 较 小时是一种很好的排序方法q通常文件中记录的数量都很大，则此时直接 插入排序方法不适用q在直接插入排序的基础上减少比较的次数， 即在插入Ri时改用二分法比较找插入位置， 便得到二分法插入排序 10q二分法插入排序必须采用顺序存储方式二分法插入排序的算法初始化 申明temp为记录结点类型i记录长度？temp=下标为i的记录left=right?left=0,right=i-1mid=(left+right)/2Temp的关键码以mid 为

5、下标的记录关键码right=mid-1endNYYNY left=mid+1ANBB将记录按找到的位置向后移动C11二分法插入排序的算法(续)left != i？找到插入位置将temp插入 recordleft=tempY下标为i的记录位置不变ANC12选择排序q基本方法是每步从待排序记录中选出排序码最小的记录 ，顺序放在已排序的记录序列的后面，直到 全部排完。u直接选择排序u堆排序13直接选择排序q方法是u首先在所有记录中选出排序码最小的记录 ，与第一个记录交换u然后在其余的记录中再选出排序码最小的 记录与第二个记录交换u以此类推，直到所有记录排好序14q初始序列为 49,38,65,97,

6、49,13,27,76(1)49 38 65 97 49 13 27 76 (2)1338 65 97 49 49 27 76 (3)13 2765 97 49 49 38 76 (4)13 27 3897 49 49 65 76 (5) 举 例15交换排序q基本方法：u两两比较待排序记录的排序码， 交换不满足顺序要求的偶对，直 到全部满足为止q种类：u起泡排序方法u快速排序方法16起泡排序方法q通过相邻记录之间的比较与交换，使值较小( 大)的记录逐步从后向前移，就像水底的气泡 一样向上冒，故称为起泡排序q基本思想uRi与Ri+1比较，若前者大于后者，则两个记 录交换位置，否则不交换u从(R0

7、，R1)到(Rn-2，Rn-1)的n-1次比较和 交换过程称为一次起泡。经过这次起泡，n 个记录中最大者被安置在第n个位置上u再对前n-1个记录进行同样处理 ，这样 最多做n-1次起泡就能完成排序。 17q改进：可以设置一个标志noswap表示本次起泡 是否有记录交换，如果没有交换则表示整 个排序过程完成起泡排序方法18初始序列: 49 38 65 97 76 13 27 49 第一趟起泡 38 49657613274997 第二趟起泡 38 49651327497697 第三趟起泡 38 49132749657697 例 题19快速排序方法q快速排序是对起泡排序的改进u起泡排序在相邻两个记录

8、间比较和交换 ，每次交换只能上移或下移一个位置，导 致总的比较与移动次数增多q快速排序又称分区交换排序，是由 C.A.R Hoar提出的u快速排序方法记录间比较次数较少，因 而速度较快，被认为是较好的排序方法20q设待排序的n个记录R0, R1, Rn-1存放在数组R中 ，选取第一个记录R0为标准q一趟快速排序快速排序是寻找记录R0的最终位置，若 一趟排序完毕后，数组分为两个部分uR0,Ri-1 存放的为小于R0的记录uRi+1,Rn-1 存放的为大于R0的记录ui为R0的最终位置q把当前参加排序的记录按Key分成前后两个部分的过 程称为对两个子序列分别重复上述过程，直到所有记 录都排好序快速

9、排序基本思想21q设置变量i指向参加排序的序列中第一个位置0 ，变量j指向参加排序的序列中最后位置n-1q首先保存记录R0，uR0为空出的位置，空位在前一区;u令j向前扫描，寻找小于R0的记录，找到小于R0的记 录Rj，将记录Rj移到当前空位中,Rj为空位在 后一区;u令i向后扫描，寻找大于R0的记录，找到大于R0的记 录Ri，将记录Ri移到当前空位中，空位到了前一 区;u再令j自j-1起向前扫描q如此交替改变扫描方向，从两端向中间靠拢， 直到i=j，这时i所指的位置为R0的最终位置快速排序实现策略22初始序列为49, 38, 65, 97, 76, 13, 27, 49例 题(1)一次分区过

10、程如下 j向左扫描 49 38659776132749ij i向右扫描 27 3865977613 49 ij J向左扫描 27 38 97 7613 6549i j 23例 题(续)i向右扫描 27 38 13 97 76 6549i j j向左扫描，位置不变 27 38 13 76 976549i j i=j,找到R0的最终位置 27 38 13 49 76 976549ij 递归处理R0的左/右区间24分配排序是一种借助多关键码排序思 想对单逻辑关键码排序的方法分配排序*25q例子扑克牌排序u要求:每张扑克牌具有两个属性花色(梅 花方块红心黑桃)和面值 (2310JQKA)，且花色的 地

11、位高于面值，排序后为梅花2，梅 花A，方块2，方块A，红心2，红 心A，黑桃2，黑桃A分配排序算法26分配排序例q排序有以下两种方法第一是先将牌按花色分成4堆，然后将每堆按 面值从小到大排序，最后按花色从小到大迭 在一起第二种是先将牌按面值大小分成13堆，然后从 小到大把它们收集起来，再按花色分成4堆 ，最后顺序地收集起来27分配排序算法一般情况下，假设文件F有n个记录 F=(R0，R1，Rn-1) 且每个记录Ri中含有d个关键码(ki0, ki1, kid-1)， 则文件F对关键码(k0,k1,kd-1)有序是指u文件中任意两个记录Ri和Rj(0ijn-1)满 足词典次序有序关系 (ki0,

12、 ki1, kid-1) (kj0, kj1, kjd-1) 其中k0称为最高位关键码，kd-1称为最低位关 键码28q实现多关键码排序，有两种方法q高位优先法:u先对最高位关键码k0排序，将文件分成若干堆每 堆中的记录都具有相同的k0u然后分别就每堆对关键码k1排序，分成若干子堆 ，如此重复，直到对kd-1排序u最后将各堆按次序叠在一起成为一个有序文件q低位优先法:u从最低位关键码kd-1起排序u然后再对高一位关键码kd-2排序u如此重复，直到对K0排序后便成为一个有序文件分配排序算法(续)29q低位优先法比高位优先法简单u高位优先排序必须将文件逐层分割成若干 子文件，然后各子文件独立排序u

13、低位优先排序不必分成子堆，对每个关键 码都是整个文件参加排序，且可通过若干次 “分配”和“收集”实现排序q基数排序就是用低位优先法对单逻辑关 键码排序的一种方法分配排序算法(续)30方法:把每个排序码看成是一个d元组 Ki=(Ki0, Ki1, Kid-1) 其中每个Ki都是集合C0，C1，Cr-1 (C0C1Cr-1)中的值 即C0KijCr-1(0in-1,0jd-1) 其中r称为基数q排序时先按Kid-1从小到大将记录分配到r个堆中q然后依次收集，再按Kid-2分配到r个堆中q如此反复，直到对Ki0分配、收集，得到的便是 排好序的序列基数排序31基数排序方法(续)q基数排序时，为了实现记

14、录的分配和收集 ，可以设r个队列，排序前为空队列，分 配时将记录插入到各自的队列中，收集 时将队列中的记录排在一起32基数排序例 (1)(1)初始状态初始状态36516989547323648103651698954732364810 (2)第一趟分配后(3)(3)第一趟收集后第一趟收集后10325953616364798481032595361636479848 33基数排序例(续)(4)第二趟分配后(5)第二趟收集后5101632363647489598 34归并排序的主要思想是q把待排序的文件分成若干个子文件，先将每 个子文件内的记录排序q再将已排序的子文件合并，得到完全排序的 文件u合

15、并时只要比较各子文件第一个记录的排序码， 排序码最小的记录为排序后的第一个记录，取出 该记录u继续比较各子文件的第一个记录，记录，找出排 序后的第二个记录u如此反复，经过一次扫描，得到排序结果归并排序*35q设文件中有n个记录，可以看成n个子文件，每 个子文件中只包含1个记录u先将每两个子文件归并，得到n/2个部分排序的 较大的子文件，每个子文件包含2个记录u再将子文件归并，如此反复，直到得到一个文 件q上述每步归并都是将两个子文件合成一个子文 件，称为“二路归并排序”。q类似地还有“三路归并排序”或“多路归并排序”二路归并排序36示 例 37q排序算法之间的比较主要考虑以下几个方面 l算法的时间复杂度l算法的辅助空间l排序的稳定性l算法结构的复杂性l参加排序的数据的规模q各种排序算法的时间复杂度与辅助空间及算 法的稳定性如下表所示各种排序方法的比较38q各种排序算法的时间复杂度与辅助空间及算法的稳定性如下表所 示 排序方法平均时间复杂度空间复杂