资源描述：
《选修1《排序》ppt课件 高中信息技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、排序排序是数据处理中经常使用的一种重要运算研究问题:如何进行排序如何进行高效率排序1排序的基本概念假设条件:假定排序的对象是由一组记录组成的文件，记录由若干字段组成，以排序码为依据排序排序码-记录中的一个(或多个)字段关键码-此时按关键码排序、排序的结果唯一不是关键码-则可能有多个记录具有相同的排序码，排序的结果不唯一2排序:设{R0,R1,…,Rn-1}是由n个记录组成的文件，{K0,K1,…,Kn-1}是排序码集合，排序是将记录按排序码不增(或不减)的次序排列排序的稳定与不稳定基本概念3按排序方法:插入排序选择排序交换排序分配排序归并排序按排序中
2、涉及的存储器不同:内排序:待排序的记录在排序过程中全部存放在内存的外排序:如果排序过程中需要使用外存的排序的种类4排序的基本操作比较比较两个关键字的大小必须操作移动将一个记录从一个位置移动到另一个位置非必须操作,可通过存储方式来避免(如静态链表)5评价排序算法好坏的标准执行算法所需的时间执行算法所需要的附加空间算法本身的复杂程度也是考虑的一个因素排序的时间开销是算法好坏的最重要的标志排序的时间开销衡量标准:算法执行中的比较次数算法执行中的移动次数排序算法的评价6金手指考试网http://www.jszksw.net/2016年金手指驾驶员考试科目一科
3、目四 元贝驾考网http://www.yuanbeijiakao.net科目一科目四仿真考试题C1Grammar7插入排序基本方法∶每步将一个待排序的记录，按其排序码大小插到前面已经排序的文件中的适当位置，直到全部插入完为止。种类：直接插入排序二分法插入排序表插入排序shell排序8直接插入排序方法:假设待排序的n个记录{R0,R1,…,Rn-1}存放在数组中，插入记录Ri时，记录集合被划分为两个区间[R0，Ri-1]和[Ri，Rn-1][R0，Ri-1]已经排好序[Ri，Rn-1]是当前未排序的部分将排序码Ki与Ki-1，Ki-2，…，K0依次比
4、较，找出应该插入的位置，将记录Ri插入，原位置的记录向后顺移直接插入排序采用顺序存储结构9直接插入排序的算法初始化申明temp为记录结点类型j=i-1将关键码比temp大的记录后移record[j+1]=record[j]继续向前比较j--endi<记录长度？Ntemp=下标为i的记录Ytemp关键码<以j为下标记录的关键码并且j>0Yj!=i-1？NY找到插入位置将temp插入record[j+1]=tempAA下标为i的记录位置不变N10二分法插入排序直接插入排序的算法简洁，容易实现，n较小时是一种很好的排序方法通常文件中记录的数量都很大，则此时
5、直接插入排序方法不适用在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序11二分法插入排序必须采用顺序存储方式二分法插入排序的算法初始化申明temp为记录结点类型i<记录长度？temp=下标为i的记录left<=right?left=0,right=i-1mid=(left+right)/2Temp的关键码<以mid为下标的记录关键码right=mid-1endNYYNYleft=mid+1ANBB将记录按找到的位置向后移动C12二分法插入排序的算法(续)left!=i？找到插入位置将temp插入rec
6、ord[left]=tempY下标为i的记录位置不变ANC13选择排序基本方法是每步从待排序记录中选出排序码最小的记录，顺序放在已排序的记录序列的后面，直到全部排完。直接选择排序堆排序14直接选择排序方法是首先在所有记录中选出排序码最小的记录，与第一个记录交换然后在其余的记录中再选出排序码最小的记录与第二个记录交换以此类推，直到所有记录排好序15初始序列为49,38,65,97,49’,13,27,76(1)4938659749’132776└────────┘(2)[13]38659749’492776└────────┘(3)[1327]6597
7、49’493876└──────┘(4)[132738]9749’496576└─┘(5)……举例16交换排序基本方法：两两比较待排序记录的排序码，交换不满足顺序要求的偶对，直到全部满足为止种类：起泡排序方法快速排序方法17起泡排序方法通过相邻记录之间的比较与交换，使值较小(大)的记录逐步从后向前移，就像水底的气泡一样向上冒，故称为起泡排序基本思想Ri与Ri+1比较，若前者大于后者，则两个记录交换位置，否则不交换从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交换过程称为一次起泡。经过这次起泡，n个记录中最大者被安置在第n个位置上再对前n-1
8、个记录进行同样处理……，这样最多做n-1次起泡就能完成排序。18改进：可以设置一个标志noswap表示本次起
