数据结构排序算法.ppt

《数据结构排序算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章排序本章要求【教学目的】掌握内排序方法的插入排序；选择排序；交换排序；基数排序；归并排序；排序的存储方式：连续地址、静态链表、索引；稳定的和不稳定的排序方法的判定方法，常见的稳定的排序方法和的不稳定的排序方法。了解外部排序的方法以及外部排序方法的特点。【教学重点】每种排序方法的算法及算法的性能分析【教学难点】排序方法的比较及稳定性的确定第八章查找一、基本概念二、插入排序三、交换排序四、选择排序五、归并排序一、基本概念排序的目的排序是为了通过关键字高效的查找相关的记录排序就是要调整原文件中的记录顺序，使之按关键字递增(或递减)次序排列起来。其形式化定义描述如下：输入：n个记录r1，r2，…

2、，rn，其相应的关键字分别为k1，k2，…，kn输出：rl′，r2′，…，rn′，使得k1′≤k2′≤…≤kn′。(或k1′≥k2′≥…≥kn′)//有序升序或者降序一、基本概念排序的数据结构待排序的记录采用顺序存储，待排序记录的定义为：#defineMAXSIZE100/*假定顺序表的最大长度为100*/typedefintKeyType；/*假定关键字类型为整数类型*/typedefstruct{KeyTypekey；/*关键字项*/OtherTypeother；/*其他项*/}DataType；/*数据元素类型*/typedefstruct{DataTyper[MAXSIZE+1]；/*

3、r[0]闲置或充当哨兵*/intlength；/*顺序表长度*/}SqList；/*顺序表类型*/一、基本概念排序的数据结构排序的稳定性：若存在关键字相同的多个记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；否则则称这种排序方法是不稳定的。排序的分类：按是否涉及数据的内、外存交换分类：内排序、外排序。内部排序方法有：插入排序、选择排序、交换排序、归并排序排序的效率分析：时间代价和空间代价二、插入排序基本思想通过构建有序序列，将待排序的数据，在已排好序的序列中从后向前扫描，找到其相应位置并进行插入操作。直接插入排序二分法插入排序Shell排序二、插入排序直接插

4、入排序算法思想：将待插入子序列元素逐步插入到有序子序列中，设有一待排序序列S={r1，r2，r3，…，ri，…，rn},其中{r1，r2，…，ri}(1≤i≤n)是按照关键字{k1≤k2≤…≤ki}有序的子序列，序列{ri+1，…，rn}无序。从序列{ri+1，…，rn}的第一个元素ri+1开始取数据元素，每取一个元素就将其插入到前面的有序序列中，并使插入后的序列有序，直到所有元素插入完成，得到一个有序序列。二、插入排序直接插入排序算法：voidStraightInsertSort(SqList*S){/*对顺序表s中的s->r[1..length]作直接插入排序*/for(i=2；i<=S-

5、>length；i++){S->r[0]=S->r[i]；/*复制为哨兵*/j=i-1;while(S->r[0].keyr[j].key){S->r[j+1]=S->r[j]；j--;}/*记录后移*/S->r[j+1]=S->r[0]；/*插入到正确位置*/}}能不能改为<=?二、插入排序直接插入排序效率分析：空间效率：用了一个辅助单元r[0]，因此辅助空间为O(1)时间效率：最好情形：待排序序列中各数据元素在排序前已按关键字大小排好序，总的比较次数=n-1次,总的移动次数=n-1次,所以时间复杂度为O（n）最坏情形：待排序序列中各数据元素为逆序状态时，直接插入排序是稳定的排序算法

6、二、插入排序二分插入排序算法思想：在插入第i个关键码时，前i－1个关键已经有序，可以通过折半的方式找到插入点。但是，虽然可以更快地找到插入点，但意义不大？因为，找到插入点后还需要进行移动元素，并没有改变移动元素的次数，因此其时间复杂度并没有发生改变。二、插入排序Shell排序算法思想：先将待排序列分割为若干个子序列分别进行直接插入排序；待整个序列基本有序时，再对全体记录进行一次直接插入排序。也称缩小增量的直接插入排序。二、插入排序Shell排序算法：voidShellInsert(SqList*s，intgap)//步长为gap的插入排序{for(i=gap+1；i<=S->length；i+

7、+)if(S->r[i].keyr[i-gap].key){/*小于时，需将r[i]插入有序表*/S->r[0]=S->r[i]；/*为统一算法设置监视哨*/for(j=i-gap；j>0&&S->r[0].keyr[j].key；j=j-gap)S->r[j+gap]=S->r[j]；/*记录后移*/S->r[j+gap]=S->r[0]；/*插入到正确位置*/}/*if*/}/