数据结构与算法教程 朱明方 吴及 第7章 排序

《数据结构与算法教程 朱明方 吴及 第7章 排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章排序7.1交换排序一.冒泡排序二.快速排序7.2插入排序一.直接插入排序二.对分插入排序三.希尔排序7.3选择排序一.简单选择排序二.堆排序第七章排序7.4归并排序一.归并排序的概念二.相邻有序子表的归并三.二路归并排序的实现7.5分配排序一.多关键字排序二.基数排序7.6内排序方法比较一.几种内部排序方法的性能二.比较分析三.方法选择第七章排序7.7拓扑分类的实现一.基本思路二.实现步骤三.算法描述7.8外排序简介一.外排序的基本步骤二.外排序的时间开销三.败者树与最佳归并树第七章排序排序(sorting)——用某种方法，把元素的无序序列调整为按某数据项有序排列的过程；数

2、据表——待排序的数据元素的有限集；有序表——排序后的表；无序表——排序前的表；主关键字——可以唯一标识数据表中各元素的数据项；排序项——用于排序的数据项；排序码——排序项的值；正序——关键字ki、kj在表中的位置关系符合排序要求；逆序——关键字ki、kj在表中的位置关系不符合排序要求；第七章排序排序结果唯一性：若以主关键字为排序项，排序结果唯一；否则排序结果不唯一；排序方法的稳定性：如果有排序码Ki=Kj，排序前Ki领先于Kj(i

3、存中进行；外排序——排序过程中需要不断地在内存与外存间交换数据；若设定待排序表为顺序表，表中元素为记录类型，则待排序表的类型可以定义如下：typedefstruct//定义待排序表的记录类型{KeyTypekey；//记录关键字约定为简单类型fieldotherdata；//记录的其他数据项}RecType；typedefstruct//定义待排序表的结构{RecTyperec[MaxSize]；//存放待排序表元素的向量intlen；//待排序表长度}SqList；在上述定义下，讨论典型的内排序方法及其实现；第七章排序7.1交换排序交换排序——通过交换元素在表中的位置使其有序的

4、排序方法一.冒泡排序(bubblesort)——简单排序方法1.基本思路经过多遍比较及交换相邻元素实现排序；——蛮力法排序过程(以非递减有序为例)：反复扫描待排序表，扫描过程中做：①每一趟(扫描无序表一次)扫描将“最大者沉到底”——依次比较相邻元素并使之有序；②每一趟扫描，记录本趟扫描中最后一次发生元素交换的前一个位置；③记录每一趟扫描是否进行过元素交换；④直到某一趟扫描无元素交换发生，则排序完成；7.1交换排序例，对无序表(4938659776132744)做冒泡排序(非递减)，第一趟排序过程：①4938659776132744第一趟排序结果:38496576132744977

5、.1交换排序对无序表(4938659776132744)进行冒泡排序，全过程：①4938659776132744②3849657613274497③3849651327447697④3849132744657697⑤3813274449657697⑥1327384449657697无交换发生，已排序；7.1交换排序2.算法描述voidBubbleSort(SqList*L){RecTypetemp；inti,j,flag；flag=L->len-1;//flag记录一趟比较中最后一次发生交换的位置while(flag>0){j=flag-1;flag=0；//j记下要比较的最后位

6、置，重置flag初值for(i=0;i<=j;i++)//进行一趟比较使相邻元素正序if(L->rec[i].key>L->rec[i+1].key){temp=L->rec[i]；L->rec[i]=L->rec[i+1]；L->rec[i+1]=temp；flag=i；}}}7.1交换排序注意：算法中，flag既是一趟扫描有无交换发生的标记，又是最后一次发生交换的位置记录；3.算法分析：时间复杂度：最坏情况，对无序表扫描n-1趟，每次下沉一个元素；共进行n(n-1)/2次比较，复杂度为O(n2)空间复杂度：inplace动态性能：稳定(在消除逆序过程中没有产生新的逆序)；思考

7、：该算法扫描过程中，“大者”下沉速度大于“小者”上浮速度；若能加速“上浮”速度，则可提高效率。如何改进？7.1交换排序二.快速排序快速排序(QuickSort)——冒泡排序的改进基本思想：——分治法大的待排序表小的待排序表更小的待排序表…2个(或1个)元素排序。实现方法：通过一趟排序把待排序表分成前后两部分，使前一部分元素的排序码≤后一部分元素的排序码；再对每部分元素以同样方法进行排序，直到全表元素按排序码有序；关键：如何把待排序表分为符合上述要求的两部分——线性表分割；7.1交