数据结构第9章 排序.ppt

《数据结构第9章 排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第九章排序宋会英2概述插入排序（直接、折半、希尔（重点））快速排序（重点）交换排序（气泡）选择排序（直接、堆（重点））归并排序分配排序（基数）第九章排序3概述排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist):是待排序数据元素的有限集合。排序码(key):通常数据元素有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分元素,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。4排序算法的稳定性:如果在元素序列中有两个元素r[i]和r[j],它们的排序码k[i]==k[j],且在排序之前,元素r[i]排在r[

2、j]前面。如果在排序之后,元素r[i]仍在元素r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据元素全部存放在内存的排序；外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。5排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受元素排序码序列初始排列及元素个数影响较大的，需要按最好情况和最坏情况进行估算。算法执行时所需的附加存储

3、:评价算法好坏的另一标准。69.2插入排序(InsertSorting)基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上,直到元素全部插入为止。基本思想是:当插入第i(i≥1)个元素时，前面的V[0],V[1],…,V[i-1]已经排好序。这时，用V[i]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移。9.2.1直接插入排序(InsertSort)7各趟排序结果21254925*1608012345012345temp21254925*160825i=1012345

4、temp21254925*160849i=28012345i=4i=5i=3012345temp21254925*160816012345temp21254925*160825*012345temp21254925*160808921254925*1608012345i=4时的排序过程完成1616012345temp21254925*08164916012345temp21254925*0816i=4j=2i=4j=3102516012345temp214925*08162525*1621254925*0801234516i=4j=1i=4j=0i=4j=-1012345temp

5、21254925*0816211611算法分析设待排序元素个数为currentSize=n,则该算法的主程序执行n-1趟(第一个元素不用插入)。排序码比较次数和元素移动次数与元素排序码的初始排列有关。最好情况下，排序前元素已按排序码从小到大有序，每趟只需与前面有序元素序列的最后一个元素比较1次，总的排序码比较次数为n-1,元素移动次数为0。21254925*160801234512最坏情况下,第i趟时第i个元素必须与前面i个元素都做排序码比较,并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和元素移动次数RMN分别为：21254928160801234513平均情况下

6、排序的时间复杂度为o(n2)。直接插入排序是一种稳定的排序方法。基本思想是:设在顺序表中有一个元素序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的元素。在插入V[i]时,利用折半搜索法寻找V[i]的插入位置。折半插入排序的算法#include"dataList.h"折半插入排序(BinaryInsertsort)14templatevoidBinaryInsertSort(dataList&L,constintleft,constintright){//利用折半搜索,在L.Vector[left]到L.Vec

7、tor[i-1]中//查找L.Vector[i]应插入的位置,再进行插入。Elementtemp;inti,low,high,middle,k;for(i=left+1;i<=right;i++){temp=L[i];low=left;high=i-1;while(low<=high){//折半搜索插入位置middle=(low+high)/2;//取中点15if(temp