数据结构-2002_第七章排序课件.ppt

数据结构-2002_第七章排序课件.ppt

ID:57001732

大小:504.50 KB

页数:77页

时间:2020-07-26

数据结构-2002_第七章排序课件.ppt_第1页
数据结构-2002_第七章排序课件.ppt_第2页
数据结构-2002_第七章排序课件.ppt_第3页
数据结构-2002_第七章排序课件.ppt_第4页
数据结构-2002_第七章排序课件.ppt_第5页
资源描述:

《数据结构-2002_第七章排序课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第七章排序7.1交换排序7.4归并排序冒泡排序一.二路归并排序快速排序二.文件归并排序7.2插入排序7.5拓扑分类直接插入排序对分插入排序2-路插入排序希尔排序对7.3选择排序一.简单选择排序二.堆排序第七章排序排序(sorting)——用某种方法,把元素的无序序列调整为按某数据项有序序列的过程。有序表——排序后的表;无序表——排序前的表。排序项——用于排序的数据项;排序码——排序项中的值。若以主关键字为排序项,排序结果唯一,否则排序结果不唯一。如果有排序码Ki=Kj,排序前Ki领先于Kj(i<

2、j),若所采用的排序方法,使得:排序后仍保持Ki领先Kj——排序方法是稳定的;排序后可能使Kj领先于Ki——排序方法不稳定。内部排序——排序过程全部在内存中进行。按照排序所采用的策略不同,内部排序可分为多类。本章讨论交换排序、插入排序、选择排序、归并排序四类排序;同时介绍拓扑分类及其实现的基本方法.7.1交换排序交换排序——通过交换元素在表中的位置使其有序的排序方法。一.冒泡排序(bubblesort)1.基本思路经过多遍比较及交换相邻元素实现排序。排序过程:反复扫描待排序表,扫描过程中做:①每

3、一趟(扫描无序表一次)扫描将“最大者沉到底”——依次比较相邻元素并使之有序;②每一趟扫描,记录本趟扫描中最后一次发生元素交换的前一个位置;③记录每一趟扫描是否进行过元素交换;④直到某一趟扫描无元素交换发生,则排序完成。7.1交换排序一.冒泡排序(bubblesort)例如,对无序表(4938659776132744)进行冒泡排序(非递减),过程如下:①4938659776132744②3849657613274497③3849651327447697④3849132744657697⑤38132

4、74449657697⑥1327384449657697无交换发生,已排序。7.1交换排序一.冒泡排序(bubblesort)2.算法简单算法语言描述P164注意:算法中,F既是一趟扫描有无交换发生的标记,又是最后一次发生交换的位置记录。算法分析:时间复杂度:最坏情况,对无序表扫描n趟,每次下沉一个元素。共进行次比较,复杂度为O(n2)空间复杂度:inplace动态性能:稳定(在消除逆序过程中没有产生新的逆序)。思考:①算法的C语言描述②该算法扫描过程中,“大者”下沉速度大于“小者”上浮速度;若

5、能加速“上浮”速度,则可提高效率。如何改进?7.1交换排序二.快速排序快速排序(QuickSort)——冒泡排序的改进。基本思想:通过一趟排序把待排序表分成前后两部分,其中前一部分元素的排序码均不大于后一部分元素的排序码;然后对每部分元素以同样的方法进行排序,直到全表元素按排序码有序。关键:如何把待排序表分为符合上述要求的两部分—线性表分割。1.线性表分割设待排序表为L,进行非递减排序,一趟排序的分割过程为:①设置指针i、j分别指向线性表的第一个和最后一个元素;②选取一个元素L(k),做L(k)

6、T,L(i)L(k);③将j逐渐减小,同时逐次比较L(j)与T,直到L(j)T时,则把L(i)移到L(j)的位置上,即L(i)L(j);⑤反复做③、④,直到i=j为止,此时令L(i)=T。例如,分割无序表(6538499776132744),取L(k)=49T65389776132744386597761327444438659776132744

7、3897761327654438279776136544382776139765443827137697384438271349769738iiiiiiiijjjjjjjj7.1交换排序二.快速排序1.线性表分割线性分割的算法描述P167思考:算法的C语言描述?2.快速排序算法从快速排序的步骤可以看出,快速排序的过程即是对无序表逐层分割的过程。是一个递归的过程。如图:排序的最小子表——表中多于一个元素——递归过程的边界。即:表起始位置<表终止位置。i-1ii+1m'i'n'mn7.1交换排序二.

8、快速排序2.快速排序算法设待排序表为L(m:n),其中:m——待排序表起始位置,n——待排序表终止位置;split(l,m,n)为一趟分割无序表L的函数,且返回本趟分割点。快速排序递归算法的C语言描述为:qksort(l,m,n)intm,n;eletyl[];{inti;if(n>m)//表长大于2{i=split(l,m,n);//分割表Lqksort(l,m,i-1);//对前半部分做快速排序qksort(l,i+1,n);//对后半部分做快速排序}return;}7.1交换排序二.快速排

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

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

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