插入排序解析课件.ppt
《插入排序解析课件.ppt》由会员分享,可在线阅读,更多相关《插入排序解析课件.ppt(62页珍藏版)》请在三一办公上搜索。
1、概述插入排序快速排序选择排序归并排序,第八章 内部排序,8.1 概 述,排序:将一个数据元素的任意序列,重新排列成一个按关键字有序的序列。数据表(datalist):它是待排序数据对象的有限集合。主关键字(key):数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据,称为关键字。也称为排序码。,排序方法的稳定性:如果在对象序列中有两 个对象Ri和Rj,它们的排序码 Ki=Kj,且在排序之前,对象Ri排在Rj前面。如果在排序之后,对象Ri仍在对象Rj的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据对象全部
2、存放在内存的排序;外排序是指在排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内、外存之间移动的排序。,排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。,内排序分类,依不同原则插入排序、交换排序、选择排序、归并排序、和计数排序等。依所需工作量简单排序-时间复杂度O(n2)先进排序方法-时间复杂度O(n logn)基数排序-时间复杂度O(d.n),8.2 插入排序(Insert Sorting),基本思想 每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到
3、对象全部插入为止。,基本思想 当插入第i(i 1)个对象时,前面的V0,V1,Vi-1已经排好序。这时,用Vi的排序码与Vi-1,Vi-2,的排序码顺序进行比较,找到插入位置即将Vi插入,原来位置上的对象向后顺移。,直接插入排序(Straight Insert Sort),void InsertSort(SqList/插入到正确位置 算法 10.1,直接插入排序的算法,算法分析,设待排序对象个数为 n,则该算法的主程序执行n-1趟。排序码比较次数和对象移动次数与对象排序码的初始排列有关。最好情况下(正序),排序前对象已按排序码从小到大有序,每趟只需与前面有序对象序列的最后一个对象比较1次,移动
4、0次对象,总的排序 码比较次数为 n-1,对象移动次数为 0。,最坏情况下(逆序),第 i 趟时第 i 个记录必须与前面 i 个记录都做比较,并且每做1次比较就要做1次记录移动。则总排序码比较次数KCN和记录移动次数RMN分别为,在平均情况下的比较次数和记录移动次数约为 n2/4。因此,直接插入排序的时间复杂度为 O(n2)。直接插入排序是一种稳定的排序方法。,折半插入排序(Binary Insertsort),基本思想 设在顺序表中有一 个记录序列 V1,V2,Vn。其中,V1,V2,Vi-1 是已经排好序的记录。在插入Vi 时,利用折半查找法寻找Vi 的插入位置。,算法(略),8.3 快速
5、排序(Quick Sort),交换排序(Exchange Sort)两两比较待排序的记录,如发生逆序(即排列顺序与排序后的次序正好相反),则交换之,直到所有对象都排好序为止。,基本方法:设待排序对象序列中的对象个数为n。第1趟,从1到n依次比较相邻两个记录的关键字,若逆序则交换,其结果是这n个记录中,关键字最大的记录被交换到第n的位置上;第2趟,从1到n-1依次比较相邻两个记录的关键字,若逆序则交换,其结果是这n1个记录中,关键字最大的记录被交换到第n-1的位置上;一般地,第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字,若逆序则交换,其结果是这n-i+1个记录中,关键字最大的记录被
6、交换到第n-i+1的位置上;最多做n-1趟-从1到 n-(n-1)+1=2,起泡排序(Bubble Sort),21,08,25,49,25,16,21,49,25,25,16,08,21,49,25,25,16,08,初始关键字,第一趟排序,第四趟排序,第二趟排序,第三趟排序,21,49,25,25,16,08,第五趟排序,起泡排序的过程,起泡排序的算法(教材 page 16)void bubble_Sort(int a,int n)for(i=n,change=TRUE;i=2/有交换,第i趟对待排序记录序列a1,a2,an-i+1进行排序,结果将该序列中关键字最大的记录交换到序列的第n-
7、i+1个位置,其它记录也都向排序的最终位置移动。最多做n-1趟起泡就能把所有记录排好序。在记录的初始排列已为正序时,算法只执行一趟起泡,做n-1次关键字比较,不移动记录。这是最好的情形。,最坏的情形是初始序列为逆序,算法执行n-1趟起泡,第i趟做 n-i 次关键字比较,执行 n-i 次记录交换。总的关键字比较次数KCN和记录移动次数RMN为:,最坏时间复杂度为O(n2)起泡排序是一个稳定的排序方法。,快速排序(Quick Sort),基本思想:任取待排序记录序列中的某个记录(例如取第一个记录)作为基准,按照该记录的关键字大小,将整个记录序列划分为左右两个子序列:左侧子序列中所有记录的排序码都小
8、于或等于基准记录的排序码 右侧子序列中所有记录的排序码都大于基准记录的排序码基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。,分别对这两个子序列重复施行上述方法,直到所有的记录都排在相应位置上为止。基准记录也称为枢轴(或支点)(pivot)记录。,QuickSort(List)if(List的长度大于1)将序列List划分为两个子序列 LeftList 和 Right List;QuickSort(LeftList);QuickSort(RightList);将两个子序列 LeftList 和 RightList 合并为一个序列List;,快速排序算法描述,快速排序的过程,21
9、,08,25,49,25*,16,初始关键字,08,25,49,25*,16,21,08,25,49,25*,16,08,25,49,25*,16,08,25,49,25*,16,08,25,49,25*,16,21,pivotkey,一次交换,二次交换,三次交换,四次交换,完成一趟排序,i,j,i,j,j,i,08,25,49,25*,16,21,完成一趟排序,分别进行快速排序,08,25,49,25*,16,21,有序序列,08,25,49,25*,16,21,快速排序的算法void QuickSort(SqList/对右序列同样处理 算法 10.7,int Partition(SqLis
10、t 算法 10.6(b),算法Partition利用序列第一个对象作为基准,将整个序列划分为左右两个子序列。算法中执行了一个循环,只要是排序码小于基准对象排序码的对象都移到序列左侧,最后基准对象安放到位,函数返回其位置。,算法Quicksort是一个递归的算法,其递归树如图所示。,算法分析,快速排序的趟数取决于递归树的高度。如果每次划分对一个记录定位后,该记录的左侧子序列与右侧子序列的长度相同,则下 一步将是对两个长度减半的子序列进行排序,这是最理想的情况。在 n个元素的序列中,对一个记录定位所需时间为 O(n)。若设 t(n)是对 n 个元素的序列进行排序所需的时间,而且每次对一个记录正确定
11、位后,正好把序列划分为长度相等的两个子序列,此时,总的计算时间为:,T(n)cn+2T(n/2)/c 是一个常数 cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+2T(n/8)=3cn+8T(n/8)cn log2n+nT(1)=O(n log2n)可以证明,函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明:就平均计算时间而言,快速排序是所有内排序方法中最好的一个。快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数。,最大递归调用层次数与递归树的高度一致,理想情况为 log2(n+1)。因此,要求存储开销为 O(log2n)。在
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 插入 排序 解析 课件
链接地址:https://www.31ppt.com/p-2156864.html