热门搜索:

  • /?115
  • 下载费用:1 金币 ?

计算机软件基础-第七章_排序.ppt

关?键?词:
计算机软件 基础 第七 排序
资源描述:
,第七章 排 序,本章内容,排序的概念和有关知识 常用的几种排序方法的基本思想、排序过程和算法实现各种排序算法的时间复杂度分析,学生成绩表,,,,,,排序: 使一组任意排列的对象变成一组按关键字线性有序的对象。关键字: 作为排序依据的数据对象。内排序与外排序:排序过程是否全部在内存进行。,7.1 排序的基本概念,排序算法的衡量标准,排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。排序算法的稳定性 关键字相同的数据对象在排序过程中是否保持前后次序不变。 如 2, 2*,1,排序后若为1, 2*, 2 则该排序方法是不稳定的。,排序,,内部排序,外部排序,归并排序,插入排序,交换排序,选择排序,,基数排序,常用的排序算法,,直接插入排序,希尔排序,,直接选择排序,堆排序,,冒泡排序,快速排序,为简单起见,数据的存储结构采用记录数组形式,同时假定关键字是整数。记录数组的类型说明如下:,typedef struct { keytype key; /*datatype other;*/ } DataType;? DataType R[n];,typedef int keytype;,其中: n为记录总数加1,7.2 插入排序,每次将一个待排序的对象,按其关键字大小,插入到前面已经排序好的一组对象的适当位置上,直到对象全部插入为止。,直接插入排序(Insert Sort) 希尔排序(Shell Sort),基本原理,7.2.1 直接插入排序,基本思想:当插入第 i 个对象时,前面的 R [1],…, R[i-1]已经排好序, 此时用R[i]的关键字与R[i-1], R[i-2], … 的关键字顺序进行比较,找到插入位置即将R[i]插入, 原来位置上对象向后顺移。,R[1]---R[i-1] 有序区,R[i]---R[n-1] 无序区,初始状态: [5] 4 10 20 12 3,插入操作:,[4 5] 10 20 12 3,[4 5 10] 20 12 3,[4 5 10 20] 12 3,[4 5 10 12 20] 3,[3 4 5 10 12 20],直接插入排序,R[0],1 [ 4],2 [10],3 [20],4 [12],5 [ 3],,,,,,算法步骤:,设已排序部分(R[1],R[2]…R[i-1]) 未排序部分(R[i],R[i+1],…R[n-1])(1) R[0]=R[i];(2) R[0]与R[j](j=i-1,i-2…,1)进行比较: 若R[0]=R[j],则将R[0]插入R[j+1]位置。,初始状态: [5] 4 10 20 12 3,插入操作:,[5 4] 10 20 12 3,R[0],j=1[4],R[ j+1]=R[ 0 ];,[5 4] 10 20 12 3,[4],[5 5] 10 20 12 3,[4],,,,[4 5] 10 20 12 3,[4],R[0]=R[i]; j=i-1; /* i=2 j=1*/,while (R[ 0 ].key= a[2*i+1] 2i+1= a[2*i+2] 2i+2 (n-1)/2的结点都是叶子,因此以这些结点为根的子树都已是堆。 只需依次将序号为(n-1)/2 ,(n-1)/2 -1,...,0 的结点作为根的子树都调整为堆即可。,堆排序 ------- 建堆:,以最大堆为例进行说明,解决这一问题可采用“筛选法” 基本思想:因为a[i]的左右子树已是堆,这两棵 子树的根分别是各自子树中关键字最大的结点, 所以必须在a[i]和它的左右孩子中选取关键字最 大的结点放到a[i]的位置上。,若已知结点a[i]的左右子树已是堆,如何将以a[i] 为根的完全二叉树也调整为堆?,若a[i]的关键字已是三者中的最大者,则无须做任何调整,以a[i]为根的子树已构成堆;否则必须将a[i]和具有最大关键字的左孩子a[2*i+1]或右孩子a[2*i+2]进行交换。 假定a[2*i+1]的关键字最大,将a[i]和a[2*i+1]交换位置,交换之后有可能导致a[2*i+1]为根的子树不再是堆,但由于a[2*i+1]的左右子树仍然是堆,于是可以重复上述过程,将以a[2*i+1]为根的子树调整为堆,...,如此逐层递推下去,最多可能调整到叶结点。,23,堆排序的示例,例:关键字序列为 42,13,91,23, 24,16,05,88, n=8, 故从i=3的结点开始调整,42,13,91,23,24,16,05,88,,,,,,,,,i=3 23 筛选下一层,,13,42,13,91,88,24,16,05,23,,i=2 91 不调整,,,,,,,42,13,91,88,24,16,05,23,,,,,,,,i=1 13 筛选下两层,,,,,i=2,91,i=1,88,13,13,23,,42,88,91,23,24,16,05,13,,,,,,,,91,88,42,23,24,16,05,13,,,,,,,,i=0 42 筛选下一层,,建成的最大堆,,,91,91,,(b)第一趟排序之后,,,88,24,42,23,13,16,05,91,,,,,,,,(c)重建的堆R[0]到R[6],(d)第二趟排序之后,,,42,24,16,23,13,05,88,91,,,,,,,,(e)重建的堆R[0]到R[5],05,24,16,23,13,42,88,91,,,,,,,,(f)第三趟排序之后,,,24,23,16,05,13,42,88,91,,,,,,,,(g)重建的堆R[0]到R[4],13,23,16,05,24,42,88,91,,,,,,,,(h)第四趟排序之后,,,23,13,16,05,24,42,88,91,,,,,,,,(i)重建的堆R[0]到R[3],05,13,16,23,24,42,88,91,,,,,,,,(j)第五趟排序之后,,,16,13,05,23,24,42,88,91,,,,,,,,(k)重建的堆R[0]到R[2],05,13,16,23,24,42,88,91,,,,,,,,(l)第六趟排序之后,,,13,05,16,23,24,42,88,91,,,,,,,,(m)重建的堆R[0]到R[2],05,13,16,23,24,42,88,91,,,,,,,,(n)第七趟排序之后,,,,,,// 对a[0]到a[n-1]进行堆排序,,void HeapSort(DataType a[],int n){ int i; DataType temp; for(i=(n-1)/2; i>=0;i- -) CreatHeap(a,n,i); for(i=n-1; i>0;i- -) { temp=a[0]; a[0]=a[i]; a[i]=temp; CreatHeap(a,i,0); }},堆排序算法,//建初始堆,//进行n-1趟堆排序,//当前堆顶记录和最后一个记录交换,// a[0]到a[i-1]重建成堆,CreatHeap(DataType a[],int n,int h);为在数组a[h]到a[n]中调整a[h] , 以a[h]为根的完全二叉树构成堆,堆排序的时间复杂度,时间复杂性为O(n log2n) 空间复杂性为 O(1) 堆排序是不稳定的排序方法。,7.4 交 换 排 序,基本原理: 两两比较待排序的对象的关键字,如果发生逆序,则交换之,直到全部对象都排好序为止。,两种常见的交换排序,冒泡排序(Bubble Sort)快速排序(Quick Sort),7.4.1 冒 泡 排 序,假设待排序的n个对象的序列为R[0],R[1],..., R[n-1],起 始时排序范围是从R[0]到R[n-1]在当前的排序范围之内,自左至右对相邻的两个结点依 次进行比较,让值较大的结点往后移(下沉)(或自右至左,让值较小的 结点往前移 (上冒)) 。每趟起泡都能保证值最大的结点后移至最右边,下一遍的排序范围为前n-1个。在整个排序过程中,最多执行(n-1)遍。但执行的遍数可 能少于(n-1),这是因为在执行某一遍的各次比较没有出 现结点交换时,就不用进行下一遍的比较。,基本过程:,对整数序列 8,5,2,4,3 按升序排序(从前向后比较),85243,5,2,4,3,8,2,4,3,5,8,2,3,4,5,8,2,3,4,5,8,初始状态,第一趟,第二趟,第三趟,第四趟,大的逐渐下沉,,,,,,每趟沉下一个最大的,起泡排序示例1(从后到前比较),flag为交换标志位,,,,void BubbleSort(DataType x[],int n){ int i,j,flag=1; DataType temp; for (i=1; ix[j+1].key) { flag=1; temp=x[j]; x[j]=x[j+1]; x[j+1]=temp; } }},冒泡排序算法,最多n-1趟排序,每一趟排序需进行的比较次数,交换,冒泡排序的时间复杂度,1、在最好情况下,初始状态是递增有序的,一趟扫描 就可完成排序, 关键字的比较次数为n-1,没有记录 移动。2、若初始状态是反序的,则需要进行n-1趟扫描,每趟 扫描要进行 n-i 次关键字的比较,且每次需要移动记 录三次,因此,最大比较次数和移动次数分别为:,考虑关键字的比较次数和对象移动次数,冒泡排序是稳定的排序方法。,冒泡排序的时间复杂度,7.4.2 快 速 排 序,快速排序法是一种所需比较次数较少,目前在内部排序中速度较快的方法。基本过程: 取待排序的结点序列中某个结点的值作为控制值,采用某种方法把这个结点放到适当的位置,使得这个位置的左边的所有结点的值都小于等于这个控制值,而右边的所有结点的值都大于等于这个控制值。,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序示例,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,,temp,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,,temp,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,,temp,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,,temp,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,,temp,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,,temp,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,,temp,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,,temp,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,,temp,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,,temp,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,,temp,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,,temp,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,,temp,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,,temp,13,38,27,38,65,97,49,49,76,13,65,76,27,49,97,49,,temp,13,38,27,38,65,97,49,49,76,13,65,76,27,49,97,49,,temp,13,38,27,38,65,97,49,49,76,13,65,76,27,49,97,49,,temp,初始状态,49 38 65 97 76 13 27 49*,第一趟排序,第二趟排序,第三趟排序,排 序 结 果:,[27 38 13] 49 [76 97 65 49*],[13] 27 [38] 49 [49* 65] 76 [97],[13] 27 [38] 49 49* [65] 76 [97],13 27 38 49 49* 65 76 97,各趟排序结果:,,,while ((R[j].key >= temp.key),,,,,49,27,,,,,,,,,49,while ((R[i].key<=temp.key),27,65,/*对右端子序列进行递归*/,/*对左端子序列进行递归*/,/*基准temp定位*/,/*从左向右扫描*/,/*从右向左扫描*/,/*初始化、temp为基准*/,void QuickSort(DataType R[ ],int low,int high){ int i,j; DataType temp; i=low; j=high; temp=R[i]; do { while ((R[j].key >= temp.key)},快速排序算法,,,,,,,,,,,,,,,,,,,,,,,,快速排序示例2,快速排序的时间复杂度,1、最坏情况是每次划分选取的基准都是当前无序区中关键字最小或最大)的记录,划分的结果是基准的左边(或右边)为空, 划分前后无序区的元素个数减少一个,因此,排序必须做n-1趟, 每一趟中需做n-i次比较,所以最大比较次数为,2、最好情况是每次所取的基准都是当前无序区的“中值”记录,划分的结果是基准的左右两个无序子区的长度大致相等。最好情况的时间复杂度为O(nlog2n)。,考虑关键字的比较次数和对象移动次数,快速排序是一种不稳定的排序方法,总结:,详细见书本 p257 表9-2,本章小结,概念: 关键字,算法的时间开销(平均比较次数,平均移动次数(具体分析)),算法的稳定性算法及算法评价: 直接插入排序(原理及算法) 希尔排序(原理) 直接选择排序(原理及算法) 堆排序(原理) 冒泡排序(原理及算法) 快速排序(原理),1、下述排序算法中,稳定的是(  )  A、 希尔排序  B、直接插入排序 C、 快速排序  D 、堆排序,课堂练习,B,2、在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是( ) A、快速排序 B、冒泡排序 C、直接插入排序 D、直接选择排序,D,3、快速排序方法在( )情况下最不利于发挥其长处。A、要排序的数据量太大 B、要排序的数据中含有多个相同值C、要排序的数据已基本有序 D、要排序的数据个数为奇数,C,作业: P258 9-4 (1)希尔排序;(2)快速排序第一趟的过程及每一趟的结果 ;(3)直接插入排序;(4)直接选择排序;(5)冒泡排序(从前向后比较)。,
? 汽车智库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:计算机软件基础-第七章_排序.ppt
链接地址:http://www.autoekb.com/p-1560.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2008-2018 mywenku网站版权所有
经营许可证编号:京ICP备12026657号-3?

收起
展开