武汉工业学院ppt课件.ppt

武汉工业学院ppt课件.ppt

ID:58492438

大小:1014.00 KB

页数:51页

时间:2020-09-20

武汉工业学院ppt课件.ppt_第1页
武汉工业学院ppt课件.ppt_第2页
武汉工业学院ppt课件.ppt_第3页
武汉工业学院ppt课件.ppt_第4页
武汉工业学院ppt课件.ppt_第5页
资源描述:

《武汉工业学院ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、数据结构DataStructures第十章排序胡学钢张晶计算机与信息学院1第十章排序(sorting)第十章排序10.1概述10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6多关键字排序与基数排序210.1概述排序——将数据表(a1,a2,……,an)调整为按关键字从小(大)到大(小)排列的过程。几个术语——增排序减排序单关键字/多关键字稳定排序:排序过程中关键字相同的元素的相对次序不变。不稳定排序:排序过程中关键字相同的元素的相对次序发生变化。内部排序:所有数据在内存外部排序:

2、部分数据在内存,部分数据在外存(涉及到内外存的交换)310.1概述基本方法:插入方法交换方法选择方法归并方法基数方法评价指标:时间:比较/移动/交换元素的次数空间:辅助空间410.2插入排序直接插入排序希尔排序510.2插入排序—直接插入排序基本思想:将待排序表看作左右两部分,其中左边为有序区,右边为无序区,整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中,以构成新的有序区。610.2插入排序—直接插入排序实例用直接插入排序算法对数据表A=(12,5,4,9,5)从小到大进行排序。(125

3、495)解:5(495)12125(95)12541254(455)9(45)1259121291295for(i=2;i<=n;i++)A[i]插入到有序表中后移插入710.2插入排序—直接插入排序算法(1)voidinsertsort(elementtypeA[]){for(i=2;i<=n;i++){temp=A[i];j=i-1;while((A[j].key>temp.key)&&(j>=1)){A[j+1]=A[j];j--;}A[j+1]=temp;}}A12345n…………a1a2a3

4、a4a5an算法流程图A[j].key>temp.key&&j>=1A[j+1]=temp;A[j+1]=A[j];j--;YNi<=ntemp=A[i];j=i-1;i=2;Yreturn;N810.2插入排序—直接插入排序算法(2)voidinsertsort(elementtypeA[]){for(i=2;i<=n;i++){A[0]=A[i];j=i-1;while(A[j].key>A[0].key){A[j+1]=A[j];j--;}A[j+1]=A[0];}}A12345n…………a1a

5、2a3a4a5an0910.2插入排序—直接插入排序算法分析稳定性:稳定排序。空间性能:需要一个记录的辅助存储空间。时间性能:与数据表初始状态有关最好(有序)最坏(逆序)平均比较:n-1(n+2)(n-1)/2O(n2)移动:2(n-1)(n+4)(n-1)/2因而适用于基本有序,规模小的数据思考:能不能在进行一次插入过程中保证至少有一个元素停留在最终的位置上呢?1010.2插入排序—希尔排序基本思想:将待排序列划分为若干组,在每组内进行直接插入排序,以使整个序列基本有序,然后再对整个序列进行直接插入

6、排序。分组方法:对给定的一个步长d(d>0),将下标相差为d的倍数的元素分在一组。d的取值依次为:d1=n/2,d2=d1/2,……,dk=11110.2插入排序—希尔排序实例1008201614710550789D1=10/21234567891010082016147105507897820169100105507814D2=5/278201691001055078147891420167850105100D3=2/278914162050781001051210.2插入排序—希尔排序算法及分析v

7、oidshell_sort(elementtypeA[]){d=n/2;while(d>0){for(i=d+1;i<=n;i++){x=A[i];j=i-d;while(j>0&&x.key

8、泡排序基本思想:从一端开始,逐个比较相邻的两个元素,发现倒序即交换。这里按从后往前(从下往上)逐个比较相邻元素。1510.3交换排序—冒泡排序实例用冒泡排序算法对数据表A=(12,5,4,9,5)从小到大进行排序。解:95594455124125951245125945121259459121251610.3交换排序—冒泡排序算法简单算法:voidbubble_sort(elementtypeA[],intn){for(i=1;i<=n-1;i++)f

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。