欢迎来到天天文库
浏览记录
ID:50456389
大小:122.50 KB
页数:39页
时间:2020-03-09
《数据结构(C语言描述)教学课件斯庆巴拉第9章典型排序算法.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第9章典型排序算法排序的定义和各种排序方法的特点,排序方法“稳定”或“不稳定”的含义各种排序方法的原理、排序过程、时间复杂度的分析和实现算法内排序和外排序的区别及适用情况希尔排序、快速排序、堆排序和归并排序等高效方法是本章学习的重点和难点第9章典型排序算法9.1实例:统计学生成绩表9.2插入排序9.3选择排序9.4交换排序9.5归并排序和基数排序9.6比较各种内排序方法9.7外排序本章总结9.1实例:统计学生成绩表9.1.1问题描述9.1.2问题分析9.1.3实现算法9.1.4排序定义及相关概念9.1.1问题描述某
2、校学生报考英语四级考试,要求成绩下发后进行各专业成绩统计,此时可以按照考试成绩进行排序,也可以按照学号进行排序。9.1.2问题分析如何将原始成绩表变成有序表呢?最常用的方法就是通过互相比较来完成排序。实现过程:假设有一张登记n个学生英语四级考试成绩的表,则先从这n个人中找出学号最小的学生记录,把它排在第一位,然后对剩下的n-1个学生记录,还重复上述操作,即找出最小的,把它放在最前面。重复此过程n-1次,表中n个学生的记录就会按学号的从小到大的排列顺序有序。9.1.3实现算法成绩表中学生记录的类型定义为:(略)成绩表
3、在内存中以顺序表的形式存储,则数据类型定义为:(略)实现算法:(略)9.1.4排序定义及相关概念排序就是把一组记录按照某个关键字(或称排序码)的值的递增或递减顺序重新排列的过程。在表中的先后次序进行排序后,记录的相对次序仍然不变,则称此排序方法是稳定的,否则称此排序方法不稳定。排序分类:内排序记录量不大,可以在内存中完成整个排序过程的排序方法。外排序记录量大,需要将一部分记录放置在内存,另一部分记录放置在外存上,排序过程中需要在内外存之间多次交换数据才能得到排序结果的排序方法称为。内排序分为插入排序、交换排序、选择
4、排序、归并排序和基数排序等五类。structRtype//排序记录{KeyTypekey;//关键字域┆};#definemaxlenmaxsize//分配的存储单元个数structListSq//顺序表{Rtypee[maxlen];//0号单元空闲intlen;}数据类型定义为:9.2插入排序9.2.1直接插入排序9.2.2折半插入排序9.2.3希尔排序9.2.1直接插入排序基本思想:每一趟将一个待排序的记录,按其关键字值的大小插入到已经排好序的有序表中,直到无序表中的所有记录全部插入到有序表中为止。排序过程:
5、把线性表中的n个元素看成是一个有序表和一个无序表。开始时,有序表中只有一个元素L.stu[0],无序表为其余的n-1个元素。依次从无序表中取出一个元素,把它插入到有序表的合适位置,使之成为一个新的有序表,这称一趟排序过程。经过n-1趟排序后,无序表中的n-1个元素全部插入到有序表中,无序表变成一个空表,排序过程结束。直接插入排序的实现算法:(略)时间复杂度:最好情况是原始记录已按关键字递增有序排列,整个排序过程的比较次数为n-1次,时间复杂度为O(n)。最坏情况是原始记录按关键字递减有序排列,整个排序过程的比较次数
6、为(n+2)(n-1)/2,记录移动的次数为(n+4)(n-1)/2,时间复杂度是O(n2)。平均情况下,时间复杂度是O(n2)。直接插入排序是一种稳定的排序方法。9.2.2折半插入排序基本思想:在有序表中进行查找时,将查找合适位置的过程用折半查找来实现。折半插入排序的实现算法:(略)时间复杂度:折半插入排序减少了记录关键字之间的比较次数,而未改变记录的移动次数。折半插入排序的时间复杂度为O(n2)。9.2.3希尔排序基本思想:把记录按一定增量分组,对每组记录使用插入排序,接着减小增量,随着增量的减小,每个分组中包
7、含的记录也越来越多,到增量的值减小到1时,整个数据合并为一组,成为一个有序序列,排序过程结束。折半插入排序的实现算法:(略)时间复杂度:时间复杂度为O(nlog2n),是一种不稳定的排序方法。9.3选择排序9.3.1直接选择排序9.3.2堆排序选择排序基本思想:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字值最小的记录作为有序序列中第i个记录。9.3.1直接选择排序基本思想:每一趟排序在n-i+1(i=1,2,…n-1)个记录中选取关键字值最小的记录,并和第i(1≤i≤n)个记录交换,共重复n-1次。
8、直接选择排序的实现算法:(略)时间复杂度:直接选择排序的时间复杂度为O(),是一种不稳定的排序方法。9.3.2堆排序堆的定义:n条记录的关键字序列为{k1,k2,…,kn},当且仅当满足下列关系时,称之为堆:ki≤k2i且ki≤k2i+1或ki≥k2i且ki≥k2i+1(1≤i≤)结论:堆是一个所有非终端结点的值均不大于(或不小于)其左右孩子结点值的完全二叉
此文档下载收益归作者所有