大学数据结构(C／C++描述)-阮宏一-大学教学资料课件PPT
收藏
资源目录
压缩包内文档预览：(预览前20页/共95页)
编号：21835870
类型：共享资源
大小：1.85MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
数据结构
C++
描述
描写
阮宏
教学
资料
课件
ppt
- 资源描述：
-
大学数据结构(C／C++描述)-阮宏一-大学教学资料课件PPT,大学,数据结构,C++,描述,描写,阮宏,教学,资料,课件,ppt
- 内容简介：
-
,第 9章 内 部 排 序,9.1 基 本 概 念 9.2 插 入 排 序 9.3 选 择 排 序 9.4 交 换 排 序 9.5 归 并 排 序 9.6 基 数 排 序 9.7 各 种 排 序 方 法 比 较,9.1 基本概念,一、分类： 内部排序：全部记录都可以同时调入内存进行的排序。,外部排序：文件中的记录太大，无法全部将其同时调入内存，需要多次进行内外存交换的排序。,二、定义： 设有记录序列： R1，R2 ，Rn ，其相应的 关键字序列为： K1，K2 ，Kn ; 若存在一种确定 的关系：Kp1 = Kp2 = = Kpn ，则将记录序列： R1，R2 ，Rn 排成按该关键字有序的序列： Rp1，Rp2， ，Rpn 的操作，称之为排序。 关系是任意的，如通常经常使用的小于、大于等关系。,三、稳定与不稳定： 若记录序列中的任意两个记录 Ri、Rj 的关键字 Ki = Kj ； 如果在排序之前和排序之后，它们的相对位置 保持不变，则这种排序方法是稳定的，否则是不稳 定的。,插入排序的数据类型定义如下： typedef struct elemtype /待排序的数据记录类型 keytype key; /数据记录的关键字 anytype otherelem; /数据记录中的其他成份 datatype;,方法：将一个记录插入到已排好序的有序表中。 初始：有序表中只有 1 个记录。 排序过程：每一遍，排好序的序列将增加一个元素。 如果序列中有 n 个元素，那么最多进行n-1 遍即可。,9.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,0,1,2,36,24,10,6,12,3,4,5,36,24,24,1.直接插入排序 例：,10,6,12,9.2 插 入 排 序,0,1,2,36,24,10,6,12,3,4,5,36,24,10,6,12,9.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,24,36,24,10,6,12,9.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,6,10,12,36,12,24,9.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,6,10,12,36,24,9.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,6,10,12,24,36,8.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,6,10,12,24,36,12,8.2 插 入 排 序,1. 直接插入排序,void insertsort(datatype aMaxNum+1, int n) int i,j; for(i=2;i=n;i+) /需要n-1趟才能插入所有的记录 a0=ai; /将待插入记录ai赋予监视哨a0 j=i-1; while(a0.keyaj.key) /后移记录，留出插入空位 aj+1=aj; j=j-1; aj+1=a0; /将记录插入 ,直接插入排序算法,10,20,30,40,10,20,40,50,50,30,分析: 移动、比较次数可作为衡量时间复杂性的标准 正序时：比较次数 1 = n-1 j=1 移动次数 0,n-1,逆序时：比较次数 j = n (n-1)/2 j=1 移动次数 (j+2) = n(n-1)/2+2n j=1,n-1,n-1,O(n2),9.2 插 入 排 序,直接插入排序算法分析：,36,24,10,6,12,36,24,12,high,10,6,12,12,方法：在已排序的序列中查找下一个元素的插入位置， 将该元素插入进去，形成更长的排序序列。 如： 12 的插入位置为下标 3。 减少了比较次数，未降低时间复杂性。,low,2.折半插入排序,9.2 插 入 排 序,36,24,10,6,12,36,24,12,high,10,6,12,12,low,12,36,24,12,high,10,6,12,12,36,24,12,10,6,12,low,2.折半插入排序,注意: 找到位置时，high 指针总是指向小于待查关键字的那个最大关键字的下标地址。,退出循环,后 移,void binarysort(datatype aMaxNum+1, int n) /对顺序表s作折半插入排序 int i,j,low,high,mid; for(i=2;i=n;i+) a0=ai; /将待插入记录ai赋予监视哨a0 low=1; high=i-1; /设置初始区间 while(low=high) /该循环语句确定插入位置 mid=(low+high)/2,折半插入排序算法,if(a0.keyamid.key) low=mid+1; /插入位置在高半区中 else high=mid-1; /插入位置在低半区中 for(j=i-1;j=high+1;j-) /high+1为插入位置 aj+1=aj; /后移记录，留出插入空位 ahigh+1=a0; /将记录插入 ,3. 希尔排序缩小增量排序,基本思想： 对待排记录序列先作“宏观”调整，再作“微观”调整。,所谓“宏观”调整，指的是 “跳跃式”的插入排序。具体做法为：,将记录序列分成若干子序列，分别对每个子序列进行插入排序。,其中，d 称为增量，它的值在排序过程中，从大到小逐渐缩小，直至最后一趟排序减为 1。,例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d ,例 如：,16 25 12 30 47 11 23 36 9 18 31,第一趟希尔排序，设增量 d =5,11 23 12 9 18 16 25 36 30 47 31,第二趟希尔排序，设增量 d = 3,9 18 12 11 23 16 25 31 30 47 36,第三趟希尔排序，设增量 d = 1,9 11 12 16 18 23 25 30 31 36 47,1 2 3 4 5 6 7 8 9 10 11,void shellsort(datatype aMaxNum+1, int n) int d,i,j; for(d=n/2;d=1;d=d/2) /d是排序增量，每进行一趟排序，d都要变小 for(i=1+d;i0 /将记录插入 ,希尔排序算法描述：,要点：对具有 n 个结点的结点序列，执行 n-1 次循环。 每次循环时挑出具有最大或最小关 键字的结点。,1. 直接选择排序,9.3 选 择 排 序,index 0 1 2 3 4 ,24 10 6 12,U N S O R T E D,直接选择排序示例：,i =1,index 0 1 2 3 4 ,6 10 24 12,U N S O R T E D,9.3 选 择 排 序,i = 2,直接选择排序示例：,index 0 1 2 3 4 ,6 10 24 12,U N S O R T E D,9.3 选 择 排 序,i = 2,直接选择排序示例：,index 0 1 2 3 4 ,6 10 24 12,U N S O R T E D,9.3 选 择 排 序,i = 3,直接选择排序示例：,index 0 1 2 3 4 ,6 10 24 12,U N S O R T E D,9.3 选 择 排 序,i = 3,直接选择排序示例：,index 0 1 2 3 4 ,6 10 12 24,9.3 选 择 排 序,直接选择排序示例：,Selection Sort: How Many Comparisons?,3 compares for values1 2 compares for values2 1 compare for values 3 = 3 + 2 + 1,6 10 12 24,index 0 1 2 3 4 ,9.3 选 择 排 序,直接选择排序示例：,void selectsort(datatype aMaxNum+1,int n) datatype temp; int i,j,k; ,9.3 选 择 排 序,直接选择排序算法：,for(i=1;i=n-1;i+) /共进行n-1趟选择和交换 k=i; for(j=i;j=n;j+) if(aj.keyak.key) k=j; if (k!=i) temp=ai;ai=ak;ak=temp; ,时间复杂度 含 n 个元素的比较次数： Sum = (n-1) + (n-2) + . . . + 2 + 1 = O( n2 ),9.3 选 择 排 序,直接选择排序算法分析：,堆的定义：n 个元素的序列 k1， k2 ， ， kn ，当且仅当满足以下关系时， 称之为堆： ki = k2i ki = k2i+1 ( i = 1,2, , n/2 ) 且分别称之为小根堆和大根堆。 e.g : 序列 96, 83, 27, 11, 9 大根堆 12，36，24，85，47，30，53，91 小根堆,或,96,9,11,83,27,2,3,1,4,5,12,47,85,91,36,24,53,30,6,2,7,3,1,8,4,5,2.堆排序,大根堆,小根堆,例：关键字序列 21，25，49，25*，16，08 ，试建大根堆。,怎样建堆？,先将原始序列画成完全二叉树的形式：,完全二叉树的第一个非终端结点编号必为n/2,21,i=3: 49大于08，不必调整； i=2: 25大于25*和16，也不必调整； i=1: 21小于25和49，要调整！,49,而且21还应当向下比较！,2.堆排序,交换 1号与 6 号记录,例：对刚才建好的大根堆进行排序：,2.堆排序,08 25 21 25* 16 49,从 1 号到 5 号 重新 调整为大根堆,08,25,25*,25 08 21 25* 16 49,08,25 25* 21 08 16 49,2.堆排序,从 1号到 4号 重新 调整为大根堆,2.堆排序,从 1 号到 3号 重新 调整为大根堆,2.堆排序,16 08 21 25* 25 49,从 1 号到 2 号 重新 调整为大根堆,2.堆排序,时间复杂性的分析：,时间耗费的代价： 建堆的时间耗费 排序的时间耗费 建堆的时间耗费： 建堆的时间复杂性为 4n= O(n) 级,排序的时间耗费： T(n) = O ( nlogn ),2.堆排序,typedef struct elemtype /待排序的数据元素类型 keytype key; /数据记录的关键字 struct elemtype *lchild,*rchild; /数据记录的左右孩子指针 datatype; /堆调整,表的存储结构：,2.堆排序,void adjustheap(datatype a ,int n,int i) datatype temp=ai; /令temp暂存待排序记录ai int j; j=2*i; /令j为ai的左孩子结点的下标 while(j=n) if(jn/并用关键字较大的孩子结点取代ai,堆排序算法,i=j;j=2*i; else break; ai.key=temp.key; /调整完后，把暂存在temp中的原ai的值放入恰当的位置 ,堆排序算法,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,1. 冒泡排序,9.4 交 换 排 序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,97,97,76,76,13,13,27,27,49,49,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,9.4 交 换 排 序,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,97,97,76,76,13,13,27,27,49,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,97,97,76,76,13,13,27,27,49,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,97,97,76,76,13,13,27,27,49,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,97,13,13,27,27,49,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,97,13,13,27,27,49,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,13,97,13,27,27,49,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,13,97,13,27,27,49,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,13,27,13,27,97,49,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,13,27,13,27,97,49,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,49,38,49,38,65,65,76,97,76,13,27,13,27,49,97,49,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,13,27,38,49,49,65,76,97,13,27,38,49,49,65,76,97,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,13,27,38,49,49,65,76,97,13,27,38,49,49,65,76,97,9.4 交 换 排 序,e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。,1. 冒泡排序,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,13,27,38,49,49,65,76,97,13,27,38,49,49,65,76,97,9.4 交 换 排 序,1. 冒泡排序,结束条件： 在任何一趟进行过程中，未出现交换。,0 1 2 3 4 5 6 7 8,38,49,65,76,13,27,49,97,13,27,38,49,49,65,76,97,97,76,65,49,49,38,27,13,正序时时间复杂度： O(n)， 逆序时时间复杂度： O(n2), 平均时间复杂性 O(n2)。,9.4 交 换 排 序,冒泡排序时间复杂性:,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,j,49,界点,e.g: 将序列 49、38、65、97、76、13、27、49 用快速排序的方法进行排序。,2. 快速排序,49,i,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,49,2. 快速排序,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,27,2. 快速排序,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,27,2. 快速排序,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,27,2. 快速排序,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,65,2. 快速排序,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,65,2. 快速排序,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,13,2. 快速排序,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,13,2. 快速排序,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,97,2. 快速排序,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,97,2. 快速排序,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,97,2. 快速排序,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,一趟快速排序,2. 快速排序,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,0 1 2 3 4 5 6 7 8,界点,27,2. 快速排序,void quicksort(datatype R ,int first,int end ) /采用快速排序方法对数组R中RfirstRend区间进行排序 /开始进行递归调用时first和end的初值分别为1和n int i,j; datatype temp; i=first; j=end; temp=Ri;/给first和end赋初值，temp中存放基准记录,算法描述：,2. 快速排序,while(ij) while(ij ,快速排序算法,Ri=temp; /将本趟排序的基准记录放在它在整个序列中应处的位置该基准值将待排序序列划分为两个分区域 if(firsti-1) quicksort(R, first, i-1);/对左侧分区域进行快速排序 if(i+1end) quicksort(R, i+1, end);/对右侧分区域进行快速排序 ,快速排序算法,时间复杂度： 快速排序在平均情况下的时间复杂性为: O(nlog2n) 阶的。 通常认为是在平均情况下最佳的排序方法。,1,1,2. 快速排序,快速排序算法分析：,0 1 2 3 4 5 6 7,9,7,8,3,52,4,16,7,9,3,8,4,52,16,3,7,8,9,4,16,52,3,4,7,8,9,16,52,子表长：1,子表长：2,子表长：4,子表长：8,9.5 归并排序,二路归并排序示例：,一趟归并： void mergepass(datatype S , datatype R , int n, int len) /把数组R划分为若干个长度为len的有序表，并将其两两归并到数组S中 int i,j; i=1; /从有序表的第一个记录开始 while(i+2*len-1=n) /归并两个长度都为len的有序表 merge(S,R,i,i+len-1,i+2*len-1); i=i+len*2; if(i+len-1n) /如果最后剩下两个有序表，其中最后一个表的长度len merge(S,R,i,i+len-1,n); else /如果最后只剩下一个有序表，将其复制到S中 for(j=i;j=n;j+) Sj=Rj; ,二路归并排序算法,void mergesort(datatype R , int n) / 二路归并排序的完整算法 datatype SMaxNum; /定义辅助数组 int len=1; /先从单个记录开始归并所以令len=1 while(lenn) mergepass(S,R,n,len);/从R
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号