《排序的基本概念》PPT课件.ppt

《《排序的基本概念》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9.1排序的基本概念9.2插入排序9.3选择排序9.4交换排序9.5归并排序9.6基数排序9.7性能比较第9章排序19.1排序的基本概念1.排序:将一组杂乱无章的数据按一定的规律顺次排列起来的过程。存放在数据表中按关键字排序2.排序的目的：便于查找。3.排序算法好坏的衡量标准：(1)时间复杂度——它主要是分析记录关键字的比较次数和记录的移动次数。(2)空间复杂度——算法中使用的内存辅助空间的多少。(3)稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。4、排序的种类：分为内部排序

2、和外部排序两大类。若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。25.待排序记录在内存中怎样存储和处理？①顺序排序——排序时直接移动记录；②链表排序——排序时只移动指针；③地址排序——排序时先移动地址，最后再移动记录。注：地址排序中可以增设一维数组来专门存放记录的地址。6.内部排序的算法有哪些？——按排序的规则不同，可分为5类：插入排序、交换排序、选择排序、归并排序、基数排序——按排序算法的

3、时间复杂度不同，可分为3类：简单的排序算法：时间效率低，O(n2)先进的排序算法:时间效率高，O(nlog2n)基数排序算法：时间效率高，O(d×n)d＝关键字的位数(长度)39.2插入排序插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。常用的插入排序有：直接插入排序和希尔排序两种。一、直接插入排序1、其基本思想是：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。最简单

4、的排序法！4初始关键字序列：【13】,6,3,31,9,27,5,11第一次排序：【6,13】,3,31,9,27,5,11第二次排序：【3,6,13】,31,9,27,5,11第三次排序：【3,6,13，31】,9,27,5,11第四次排序：【3,6,9,13，31】,27,5,11第五次排序：【3,6,9,13，27,31】,5,11第六次排序：【3,5,6,9,13，27,31】,11第七次排序：【3,5,6,9,11，13，27,31】例1：关键字序列T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间

5、过程序列。注：方括号[]中为已排序记录的关键字，下划横线的关键字表示它对应的记录后移一个位置。52、C语言程序voidInsertSort(DataTypea[],intn)/*用直接插入法对a[0]--a[n-1]排序*/{inti,j;DataTypetemp;for(i=0;i-1&&temp.key

6、7,89,6,24};inti,n=6;SeqListmyList;ListInitiate(&myList);for(i=0;itypedefintKeyType;typedefstruct{KeyTypekey;}DataType;#defineMaxS

7、ize100#include"SeqList.h"7(1)时间效率：因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。其他情况下也要考虑移动元素的次数。故时间复杂度为O(n2)(2)空间效率：仅占用1个缓冲单元——O（1）(3)算法的稳定性：稳定3、直接插入排序算法分析二、希尔（shell）排序（又称缩小增量排序）1、基本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束。2、技巧：小组的构成不是简

8、单地“逐段分割”，而是将相隔某个增量dk的记录组成一个小组,让增量dk逐趟缩短（例如依次取5,3,1），直到dk＝1为止。3、优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。8例2：设待排序的序列中有