数据结构 课件 排序

1第九章排序清华大学计算机系殷人昆邓俊辉2概述插入排序交换排序选择排序归并排序基数排序第九章排序3概述排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist):它是待排序数据元素的有限集合。排序码(key):通常数据元素有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分元素,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。4排序算法的稳定性:如果在元素序列中有两个元素r[i]和r[j],它们的排序码k[i]==k[j],且在排序之前,元素r[i]排在r[j]前面。如果在排序之后,元素r[i]仍在元素r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据元素全部存放在内存的排序；外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。5排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受元素排序码序列初始排列及元素个数影响较大的，需要按最好情况和最坏情况进行估算。算法执行时所需的附加存储:评价算法好坏的另一标准。6待排序数据表的类定义#includeiostream.hconstintDefaultSize=100;templateclassTclassElement{//数据表元素定义public:Tkey;//排序码ElementT&operator=(ElementT&x){key=x.key;otherdata=x.otherdata;return*this;}7booloperator==(ElementT&x){returnkey==x.key;}//判*this与x相等booloperator=(ElementT&x){returnkey=x.key;}//判*this小于或等于xbooloperator=(ElementT&x){returnkey=x.key;}//判*this大于或等于xbooloperator(ElementT&x){returnkeyx.key;}//判*this大于xbooloperator(ElementT&x){returnkeyx.key;}//判*this小于x};8templateclassTclassdataList{//数据表类定义private:ElementT*Vector;//存储排序元素的向量intmaxSize;//向量中最大元素个数intcurrentSize;//当前元素个数public:datalist(intmaxSz=DefaultSize)://构造函数maxSize(maxSz),currentSize(0){Vector=newElementT[maxSize];}intLength(){returncurrentSize;}//取表长度9voidSwap(ElementT&x,ElementT&y){ElementTtemp=x;x=y;y=temp;}ElementT&operator[](inti)//取第i个元素{returnVector[i];}intPartition(constintlow,constinthigh);//快速排序划分};10插入排序(InsertSorting)基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上,直到元素全部插入为止。基本思想是:当插入第i(i≥1)个元素时，前面的V[0],V[1],…,V[i-1]已经排好序。这时，用V[i]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较，插入位置即将V[i]插入，原来位置上的元素向后顺移。直接插入排序(InsertSort)11各趟排序结果21254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=212012345i=4i=5i=3012345temp21254925*16081621254925*160825*012345temp21254925*1608081321254925*1608012345i=4时的排序过程完成1616012345temp21254925*08164916012345temp21254925*0816i=4j=3i=4j=2142516012345temp214925*08162525*1621254925*0801234516i=4j=1i=4j=0i=4j=-1012345temp21254925*0816211615直接插入排序的算法#includedataList.htemplateclassTvoidInsertSort(dataListT&L,intleft,intright){//依次将元素L.Vector[i]按其排序码插入到有序表//L.Vector[left],…,L.Vector[i-1]中,使得//L.Vector[left]到L.Vector[i]有序。ElementTtemp;inti,j;for(i=left+1;i=right;i++)if(L[i]L[i-1]){temp=L[i];j=i-1;16do{L[j+1]=L[j];j--;}while(j=left&&tempL[j]);L[j+1]=temp;}};算法分析设待排序元素个数为currentSize=n,则该算法的主程序执行n-1趟。排序码比较次数和元素移动次数与元素排序码的初始排列有关。17最好情况下，排序前元素已按排序码从小到大有序，每趟只需与前面有序元素序列的最后一个元素比较1次，移动2次元素，总的排序码比较次数为n-1,元素移动次数为0。最坏情况下,第i趟时第i个元素必须与前面i个元素都做排序码比较,并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和元素移动次数RMN分别为111122142221nininnniRMNnnniKCN//))(()(,//)(2218平均情况下排序的时间复杂度为o(n2)。直接插入排序是一种稳定的排序方法。基本思想是:设在顺序表中有一个元素序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的元素。在插入V[i]时,利用折半搜索法寻找V[i]的插入位置。折半插入排序的算法#includedataList.h折半插入排序(BinaryInsertsort)19templateclassTvoidBinaryInsertSort(dataListT&L,constintleft,constintright){//利用折半搜索,在L.Vector[0]到L.Vector[i-1]中查找//L.Vector[i]应插入的位置,再进行插入。ElementTtemp;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;//取中点20if(tempL[middle])//插入值小于中点值high=middle-1;//向左缩小区间elselow=middle+1;//否则,向右缩小区间}for(k=i-1;k=low;k--)L[k+1]=L[k];//成块移动,空出插入位置L[low]=temp;//插入}};算法分析折半搜索比顺序搜索快,所以折半插入排序就21平均性能来说比直接插入排序要快。它所需的排序码比较次数与待排序元素序列的初始排列无关，仅依赖于元素个数。在插入第i个元素时，需要经过log2i+1次排序码比较,才能确定它应插入的位置。因此，将n个元素(为推导方便,设为n=2k)用折半插入排序所进行的排序码比较次数为：折半插入排序是一个稳定的排序方法。1122log1logninni22当n较大时，总排序码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。在元素的初始排列已经按排序码排好序或接近有序时，直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的元素移动次数与直接插入排序相同，依赖于元素的初始排列。23链表插入排序基本思想是：在每个元素的结点中增加一个链接指针数据成员link。对于数组中的一组元素V[1],…,V[n],若V[1],……,V[i-1]已经通过指针link,按其排序码从小到大链接起来。现要插入V[i],i=2,3,…,n,则必须在前面i-1个链接起来的元素当中，循链检测比较，找到V[i]应插入的位置，把V[i]链入，并修改相应链接指针。从而得到V[1],…,V[i]的一个通过指针排好的链表。如此重复执行，直到把V[n]也插入到链表中排好序为止。24i=2i=3254925*1608012345621初始currentpreicurrentpreiprecurrentii=425i=5i=6254925*1608012345621precurrenti结果precurrenti26用于链表排序的静态链表的类定义constintDefaultSize=10;//在staticList.h文件中templateclassTstructElement{//静态链表元素类定义Tkey;//排序码，其它信息略intlink;//结点的链接指针Element():link(0){}//构造函数Element(Tx,intnext=0):key(x),link(next){}//构造函数}templateclassT27classstaticLinkedList{//静态链表的类定义public:staticLinkedList(intsz=DefaultSize){maxSize=sz;n=0;Vector=newElementT[sz];}ElementT&operator[](inti){returnVector[i];}private:ElementT*Vector;//存储元素的向量intmaxSize;//最大元素个数intn;//当前元素个数};28链表插入排序的算法#includestaticList.hconstTmaxData;//排序码集合中的最大值templateclassTintinsertSort(staticLinkedListT&L){//对L.Vector[1],...,L.Vector[n]按其排序码key排序,//L.Vector[0]做为排序后各个元素所构成的有序循//环链表的附加头结点使用L[0].key=maxData;L[0].link=1;L[1].link=0;//形成只有一个元素的循环链表29inti,pre,p;for(i=2;i=n;i++){//每趟向有序链表中插入一个结点p=L[0].link;//p是链表检测指针pre=0;//pre指向p的前驱while(L[p].key=L[i].key)//循链找插入位置{pre=p;p=L[p].link;}L[i].link=p;L[pre].link=i;//结点i链入}};30算法分析使用链表插入排序,每插入一个元素,最大排序码比较次数等于链表中已排好序的元素个数,最小排序码比较次数为1。故总的排序码比较次数最小为n-1，最大为用链表插入排序时，元素移动次数为0。但为了实