下载

0下载券

加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 数学结构课件

数学结构课件.ppt

数学结构课件

croesus
2011-03-29 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《数学结构课件ppt》,可适用于其他资料领域

数据结构课件数据结构课件内部排序第一讲年月第十章内部排序第十章内部排序插入排序:直插入排序,希尔排序交换排序:冒泡排序霍尔快速排序选择排序:简单选择排序堆排序归并排序基数排序§排序的基本概念§排序的基本概念一、排序:将若干数据元素构成的一个任意序列重新排成按关键字有序序列的过程。二、关于排序的稳定性:若排序之前Ki=Kj,并且Ri领先Rj(i<j)排序后仍Ri领先于Rj则排序是稳定的否则排序是不稳定的。三、排序方法分类:内排序:在内存进行外排序:在内存进行同时访问外存§排序的基本概念§排序的基本概念四、存储结构:顺序存储结构,常称为表。#defineMAXSIZE*表中记录的个数*Typedefstruct{intkey*或其他类型**其他次关键字域*}ElemTypetypedefElemTypelisttpMAXSIZE§插入排序§插入排序一、直接插入排序:思路:通过不断的将某记录插入到一个已经有序的表中来实现。有一组关键字{}i=(),,,┏━┛i=(,),,,i=(,,),,┏━━━━━┛i=(,,,),┏━┛end(,,,,)直接插入排序算法voidstraisort(listtpr){for(i=i<=ni){r=ri*设置监视哨*j=ik=rikeywhile(rjkey>k)*大值的记录后移*{rj=rjj}rj=r*插入位置*}}*straisort*直接插入排序算法直接插入排序算法算法分析:排序是稳定的原来:()排序后:(,,,,)排时间复杂度为:T(n)=O(n)§交换排序§交换排序一、起泡排序(由小到大)思路:第趟aj与aj比,较大数=>aj(j=,n)第趟aj与aj比,较大数=>aj(j=,n)第n趟a与a比,较大数=>a(j=,n(n))一、起泡排序(由小到大)一、起泡排序(由小到大)算法描述:()voidbublesort(listtpr){for(i=i<=ni)*共计n趟*for(j=j<=nij)if(rjkey>rjkey){x=rjrj=rjrj=x}}*bubblesort*起泡排序实例图示:排序表长度n=起泡排序实例图示:排序表长度n=初始状态第趟后第趟后第趟后第趟后第趟后第趟后起泡排序改进方法()Voidbubblesort(listtpr){i=do{bool=for(j=j<=nij)if(rjkey>rjkey){x=rjrj=rjrj=xbool=}i}while(bool==i<=n)}*bubblesort*当某一趟仅有比较而无数据交换表明序列已经有序。可以结束排序过程。起泡排序算法分析起泡排序算法分析时间复杂度:一般情况下:T(n)=(n)当原始序列有序是:T(n)=(n)起泡排序算法是稳定的。排序算法小结:排序算法小结:直接插入排序稳定时间复杂度为:(n)交换排序的起泡排序是稳定一般时间复杂度为:(n)当原始序列有序时间复杂度为:(n)上一讲内容回顾上一讲内容回顾排序基本概念插入排序直接插入排序稳定T(n)=O(n)希尔排序不稳定T(n)=n交换排序起泡排序稳定T(n)=O(n)原表有序时T(n)=O(n)本讲内容本讲内容交换排序起泡排序稳定T(n)=O(n)快速排序不稳定T(n)=O(nlogn)选择排序简单选择排序稳定T(n)=O(n)堆排序不稳定T(n)=O(nlogn)§交换排序§交换排序二、霍尔快速排序存储结构:顺序存储结构,常称为表。#defineMAXSIZE*表中记录的个数*Typedefstruct{intkey*或其他类型**其他次关键字域*}ElemTypetypedefElemTypelisttpMAXSIZE霍尔快速排序思路霍尔快速排序思路()以rkey为枢轴经过比较将:rr,………,rn分成两个子表:kikkj,左子表关键字<k右子表关键字>=k霍尔快速排序思路霍尔快速排序思路每一趟具体做法:先以第一个关键字为枢轴。设置左右两个指针分别指向表的两端i=,j=n。从表的右端开始比较(j=n),发生元素移动后再换到左端比较(i)直到i=j为止。这就是枢轴元素的最后位置。()对各个子表重复第()步直到各子表长度为为止。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/21

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利