版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、Agenda,名次排序 选择排序 冒泡排序 插入排序 基数排序 堆排序 归并排序 快速排序,1、名次排序,元素在队列中的名次(rank)可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。 例如,给定一个数组a=4, 3, 9, 3, 7作为队列,则各元素的名次为r=2,0,4,1,3。,1、名次排序,template void Rank(T a, int n, int r) /计算a 0:n-1中n个元素的排名 for (int i = 0; i n; i+) ri = 0; /初始化 /逐对比较所有的元素 for (int i = 1; i n; i+) for ( i
2、nt j = 0; j i; j+) if (a j = ai) ri+; else rj+; ,1、名次排序,template void Rearrange (T * ,根据a的元素之间所进行的比较操作来估算程序的时间复杂性。 对于i的每个取值,执行比较的次数为i,所以总的比较次数为1+2+3+ +n-1 = (n-1)n/2。 移动操作次数为:n,1、名次排序,2、选择排序,思想: 首先找出最大的元素,把它移动到an-1,然后在余下的n-1个元素中寻找最大的元素并把它移动到an-2,如此进行下去。,template int Max(T a, int n) / 寻找a 0 : n-1中的最大
3、元素 int pos = 0; for (int i = 1; i n; i+) if (apos ai) pos = i; return pos; 每次调用Max(a,size)需要执行size-1次比较。,2、选择排序,2、选择排序,template void SelectionSort (T a, int n) /对数组a 0:n-1中的n个元素进行排序 for ( int size = n; size 1; size- -) int j= Max(a, size); /size-1次比较 Swap( aj,asize-1 ) ; /移动3次 ,按照元素的比较次数来估算函数的时间复杂性。
4、 每次调用Max(a,size)需要执行size-1次比较,所以总的比较次数为: 1+2+3+n-1= (n-1)n/2。 移动次数为:3(n-1),2、选择排序,上述程序中选择排序函数的一个缺点是:即使元素已经按序排列,程序仍然继续运行。 为了终止不必要的循环,在查找最大元素期间,可以顺便检查数组是否已按序排列。,2、选择排序,template void SelectionSort(T a, int n) / 及时终止的选择排序 bool sorted = false; for(int size = n; !sorted ,2、选择排序,最好情况:数组a有序。 最坏情况:数组a最大元素在首位
5、,其他元素 已经有序。 最好 最坏 比较 n-1 n(n-1)/2 移动 3 3(n-1),2、选择排序,3、冒泡排序,采用一种“冒泡策略”把最大元素移到右部。在冒泡过程中,对相邻的元素进行比较,如果左边的元素大于右边的元素,则交换这两个元素。 在一次冒泡过程结束后,可以确信最大的元素肯定在最右边的位置上。 例: 11,15 ,3 ,9,20,7 ,1 ,在第一次冒泡过程结束后,得到?,3、冒泡排序,template void Bubble (T a, int n) /把数组a0:n-1中最大的元素通过冒泡移到右边 for ( int i = 0; i ai+1) Swap(ai,ai+1);
6、 ,3、冒泡排序,template void BubbleSort (T a, int n) /对数组a0:n-1中的n个元素进行冒泡排序 for ( int i = n; i1; i- -) Bubble(a,i) ; ,3、冒泡排序,如果在一次冒泡过程中没有发生元素互换,则说明数组已经按序排列,没有必要再继续进行冒泡过程。,3、冒泡排序,template bool Bubble(T a, int n) /把a0:n-1 中最大元素冒泡至右端 bool swapped = false; / 尚未发生交换 for (int i = 0; i ai+1) Swap(ai, ai+1); swap
7、ped = true; / 发生了交换 return swapped; ,3、冒泡排序,template void BubbleSort(T a, int n) / 及时终止的冒泡排序 for(int i = n;i1 最坏情况下比较次数,移动次数 ? 最好情况下比较次数,移动次数 ?,3、冒泡排序,最好情况:数组a最初已经有序。 最坏情况:数组a倒序。 最好 最坏 比较 n-1 n(n-1)/2 移动 0 3*n(n-1)/2,4、插入排序,算法设计: 5, 2, 4, 10, 7 5, 2, 5, 2, 4, 5, 2, 4, 5, 10, 2, 4, 5, 7, 10,4、插入排序,思想
8、:因为只有一个元素的数组是一个有序数组,所以可以从包含n个元素的数组的第一个元素开始。通过把第二个元素插入到这个单元数组中,可以得到一个大小为2的有序数组。插入第三个元素可以得到一个大小为3的有序数组。 按照这种方法继续进行下去,最终将得到一个大小为n的有序数组。,4、插入排序,template void InsertionSort(T a, int n) for (int i=1; i = 0 ,4、插入排序,最好情况:数组a最初已经有序。 最坏情况:数组a倒序。 最好 最坏 比较 n-1 n(n-1)/2 移动 n-1 n-1+n(n-1)/2,5、基数排序,一种更快的排序方法为箱子排序(
9、bin sort)。 在箱子排序过程中,节点首先被放入箱子之中,具有相同分数的节点都放在同一个箱子中,然后通过把箱子链接起来就可以创建一个有序的链表。,5、基数排序,5、基数排序,voidBinSort(Chain ,5、基数排序,在两个for循环中执行的每一次插入和删除操作所需要的时间均为(1) 因此第一个for循环的的复杂性为(n),其中n为输入链表的长度 第二个for循环的复杂性为(n+range) 因此函数BinSort总的复杂性为(n+range)(如果成功的话)。,5、基数排序,假定对范围在0999之间的10个整数进行排序。 如果使用range=1000来调用BinSort,那么箱
10、子的初始化将需要1000个执行步,节点分配需要10个执行步,从箱子中收集节点需要1000个执行步,总的执行步数为2010。,5、基数排序,不直接对这些数进行排序,而是采用一些基数r来分解这些数。 在基数排序(radix sort)中,把数按照某种基数分解为数字,然后对数字进行排序。 基数r=箱子个数,5、基数排序,5、基数排序,对于一般的基数r,相应的分解式为: x%r;(x%r2)/r;(x%r3)/r2;. 当使用基数r=n对n个介于0nc-1范围内的整数进行分解时,每个数将可以分解出c个数字。 因此,可以采用c次箱子排序,每次排序时取range=n。整个排序所需要的时间为(cn)= (n
11、)(因为c是一个常量)。,6、堆排序,先将要排序的n 个元素初始化为一个最大堆,然后每次从堆中提取(即删除)元素。各元素将按递减次序排列。 初始化所需要的时间为(n),每次删除所需要的时间为O(logn) ,因此总时间为O(nlogn) 。,6、堆排序,template void HeapSort(T a, int n) / 利用堆排序算法对a1:n 进行排序 / 创建一个最大堆 MaxHeap H(1); H.Initialize(a,n,n) ; / 从最大堆中逐个抽取元素 T x; for (int i = n-1; i = 1; i-) H.DeleteMax(x) ; ai+1 = x; / 在堆的析构函数中保存数组a H.Deactivate(x) ; ,6、堆排序,堆排序的初始化策略
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- Unit 8 Summer holiday is coming!Lesson 43 公开课教学课件【七年级英语下册(冀教版)】
- 市政工程促进城市消费升级
- 【初中语+文】《礼记》二则+课件+统编版语文八年级下册
- 2024年生化化工药品技能考试-化工设计笔试参考题库含答案
- 2024年特种作业考试-冶金(有色)生产安全作业(煤气作业)笔试参考题库含答案
- 2024年火电电力职业技能鉴定考试-电力基础知识笔试参考题库含答案
- 2024年浙江住院医师-浙江住院医师精神科笔试参考题库含答案
- 2024年法律知识法治建设知识竞赛-中医药法知识笔试参考题库含答案
- 2024年江西住院医师-江西住院医师外科笔试参考题库含答案
- 2024-2030全球与中国用触控笔的笔记App市场现状及未来发展趋势
- 抗菌药物临床应用指南培训课件
- 群文议题-“童年的滋味”教学案例
- 公路工程机械设备安全技术操作规程
- (2020年整理)医院各部门廉政风险点汇总表
- 医院病房患者心肺复苏演练脚本
- 初中心理健康教育人教七年级上册目录人贵自知教学设计 成都市龙泉第七中学校 杨继洪
- 中心校《小学编织技术》课程纲要
- (施工方案)交叉施工专项方案
- 黄家沟淤地坝工程施工组织设计
- 化学(师范)行业-专业-就业分析报告
- 2020年职业院校护理技能大赛模拟试卷-内科护理试题及答案
评论
0/150
提交评论