数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第八章 排序
94页1、第八章 排序,数据结构,第八章 排序,第八章 排序,知 识 点 排序的基本概念 三种简单的排序方法:冒泡排序、直接选择排序、直接插入排序 堆排序 快速排序 归并排序 基数排序 难 点 堆排序 快速排序 归并排序 基数排序,要 求 熟练掌握以下内容: 熟悉各种内部排序方法的基本思想和特点 各种排序方法的优缺点、时、空性能和适用场合 熟悉并掌握三种简单排序算法、快速排序算法和堆排序算法 了解以下内容: 二路归并排序算法 基数排序算法,第八章目录,8.1 排序的基本概念 8.2 三种简单排序方法 8.3 堆排序 8.4 快速排序 8.5 归并排序 8.6 基数排序 8.7 应用实例及分析 小 结 习题与练习,8.1 排序的基本概念,将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序(sort)。 对一批记录的排序,应该指定是根据记录中哪个域的数据进行排列。这个作为排序依据的数据域我们称之为关键字(key)。 本章讨论的排序均为按递增顺序排序,并假定要排序的记录均已存储在一个一维数组中。,该一维数组定义如下: #define MAXITEM 100 struct record KeyType
2、 key; /*关键字*/ ElemType data; /*其他域*/ sqlistMAXITEM;,大多数的排序方法数据是存储在内存中,并在内存中加以处理的,这种排序方法叫内部排序。 如果在排序过程中,数据的主要部分存放在外存储器中(如软盘、硬盘、磁带),借助内存进行内、外存数据交换,逐步排列记录之间的顺序,则称之为外部排序。 一种排序方法,如果排序后具有相同关键字的记录仍维持排序之前的相对次序,则称之为稳定的,否则称为不稳定的。,返回,8.2.1 简单选择排序,简单选择排序的作法是:第一趟扫描所有数据,选择其中最小的一个与第一个数据互换;第二趟从第二个数据开始向后扫描,选择最小的与第二个数据互换;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。 在每一趟扫描数据时,用一个整型变量跟踪当前最小数据的位置,然后,第i趟扫描只需将该位置的数据与第i个数据交换即可。这样扫描n-1次,处理数据的个数从n每次逐渐减1,每次扫描结束时才可能有一次交换数据的操作。,图8.1 简单选择排序,简单选择排序分析,简单选择排序在(n-1)趟扫描中共需进行n(n-1)/2次比较,最坏情况下的
3、互换次数为(n-1),整个算法的时间复杂性为O(n2)。 简单选择排序简单并且容易实现,适宜于n较小的情况。 简单选择排序是不稳定的排序算法。,简单选择排序算法,void selectsort (sqlist r, int n) int i, j, min; for (i=1;i=n-1;i+) min=i; /*用min指出每一趟在无序区范围内的最小元素*/,简单选择排序算法续,for (j=i+1;j=n-1;j+) if (rj.key rmin.key) min=j; r0 = ri; /* r0用于暂时存放元素*/ ri = rmin; rmin =r0; ,8.2.2 冒泡排序,冒泡排序是一种简单而且容易理解的排序方法,它和气泡从水中不断往上冒的情况有些类似。 其基本思想是对存放原始数据的数组,按从后往前的方向进行多次扫描,每次扫描称为一趟(pass)。当发现相邻两个数据的次序与排序要求的“递增次序”不符合时,即将这两个数据进行互换。这样,较小的数据就会逐单元向前移动,好象气泡向上浮起一样。,图8.2 冒泡排序过程,需扫描的趟数视原始数据最初的排列次序的不同而不同,最坏的情
4、况要进行(n-1)趟扫描,一般常常少于(n-1)趟即可完成。 可以设置一个标志flag用来指示扫描中有没有进行数据交换,每趟扫描开始前将其置1。当这趟扫描至少出现一次互换时,将其置0。如某趟扫描后flag仍为1,说明此趟扫描已无数据互换,则排序结束,不必再继续扫描了。,冒泡排序算法,void bubblesort(sqlist r, int n) int i,j,flag; for(i=1;i=n-1;i+) flag=1; for( j=i;j=n-1;j+) if (rj+1.key rj.key),冒泡排序算法续, flag=0; r0=rj; /* r0用于暂时存放元素*/ rj=rj+1; rj+1=r0; if (flag=1) return; ,冒泡排序算法分析,冒泡排序算法的优点是比较容易理解,且当原始数据大体符合要求的次序时,运算速度较快。 但它不是高效率的算法,在最坏的情况下,如果输入数据的次序与排序要求的次序完全相反,冒泡排序需要进行n(n-1)/2次比较和n(n-1)3/2次移动,其数量级均为O(n2)。 对于有相同关键字记录的情况,冒泡排序是稳定的。,8.2.
《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第八章 排序》由会员E****分享,可在线阅读,更多相关《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第八章 排序》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页