数据结构-排序

概述插入排序快速排序选择排序归并排序基数排序各种内排方法比较第十章内部排序概述排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据表(datalist):它是待排序数据对象的有限集合。主关键字(key):数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据，称为关键字。也称为排序码。排序方法的稳定性:如果在对象序列中有两个对象r[i]和r[j],它们的排序码k[i]==k[j],且在排序之前,对象r[i]排在r[j]前面。如果在排序之后,对象r[i]仍在对象r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。内排序分类•依不同原则插入排序、交换排序、选择排序、归并排序和计数排序等。•依所须工作量简单排序---时间复杂度o(n2)先进排序方法---时间复杂度o(nlogn)基数排序---时间复杂度o(d.n)插入排序(InsertSorting)基本思想当插入第i(i1)个对象时,前面的V[0],V[1],…,V[i-1]已经排好序。这时,用V[i]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的对象向后顺移。基本思想每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。直接插入排序(InsertSort)直接插入排序过程012345tempi=1i=2012345temp2108254925*162125084925*16252125084925*162125084925*16492125084925*16i=32125084925*1625*2125084925*16i=4i=52125084925*1616162125084925*162125084925*162125084925*1608直接插入排序的算法typedefintSortData;voidInsertSort(SortDataV[],intn){//按非递减顺序对表进行排序SortDatatemp;inti,j;for(i=1;in;i++){temp=V[i];for(j=i;j0;j--)//从后向前顺序比较if(tempV[j-1])V[j]=V[j-1];elsebreak;V[j]=temp;}}算法分析设待排序对象个数为n,则该算法的主程序执行n-1趟。排序码比较次数和对象移动次数与对象排序码的初始排列有关。最好情况下,排序前对象已按排序码从小到大有序,每趟只需与前面有序对象序列的最后一个对象比较1次,移动2次对象,总的排序码比较次数为n-1,对象移动次数为2(n-1)。最坏情况下,第i趟时第i个对象必须与前面i个对象都做排序码比较,并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和对象移动次数RMN分别为在平均情况下的排序码比较次数和对象移动次数约为n2/4。因此，直接插入排序的时间复杂度为o(n2)。直接插入排序是一种稳定的排序方法。111122142221nininnniRMNnnniKCN//))(()(,//)(22折半插入排序(BinaryInsertsort)基本思想设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半搜索法寻找V[i]的插入位置。折半插入排序的算法typedefintSortData;voidBinInsSort(SortDataV[],intn){SortDatatemp;intLeft,Right;for(inti=1;in;i++){Left=0;Right=i-1;temp=V[i];while(Left=Right){intmid=(Left+Right)/2;if(tempV[mid])Right=mid-1;elseLeft=mid+1;}for(intk=i-1;k=Left;k--)V[k+1]=V[k];//记录后移V[Left]=temp;//插入}}折半插入排序012345tempi=1i=2012345temp52133i=35521532144i=4215388i=52153161684421384516折半搜索比顺序搜索查找快,所以折半插入排序就平均性能来说比直接插入排序要快。它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第i个对象时,需要经过log2i+1次排序码比较,才能确定它应插入的位置。因此,将n个对象(为推导方便,设为n=2k)用折半插入排序所进行的排序码比较次数为：1122log1logninni算法分析当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。在对象的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列。折半插入排序是一个稳定的排序方法。折半插入排序的时间复杂度为o(n2)。希尔排序(ShellSort)基本思想设待排序对象序列有n个对象,首先取一个整数gapn作为间隔,将全部对象分为gap个子序列,所有距离为gap的对象放在同一个子序列中,在每一个子序列中分别施行直接插入排序。然后缩小间隔gap,例如取gap=gap/2，重复上述的子序列划分和排序工作。直到最后取gap==1,将所有对象放在同一个序列中排序为止。希尔排序方法又称为缩小增量排序。i=3Gap=30123452108254925*160123452108254925*16i=2Gap=22108254925*162108254925*16i=1Gap=12108254925*162108254925*16希尔排序过程typedefintSortData;voidShellSort(SortDataV[],intn){SortDatatemp;intgap=n/2;//gap是间隔while(gap!=0){//循环,直到gap为零for(inti=gap;in;i++){temp=V[i];//直接插入排序for(intj=i;j=gap;j=j-gap)if(tempV[j-gap])V[j]=V[j-gap];elsebreak;V[j]=temp;}gap=(int)(gap/2);}}希尔排序的算法开始时gap的值较大,子序列中的对象较少,排序速度较快;随着排序进展,gap值逐渐变小,子序列中对象个数逐渐变多,由于前面大多数对象已基本有序,所以排序速度仍然很快。Gap的取法有多种。shell提出取gap=n/2，gap=gap/2，直到gap=1。对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。希尔排序所需的比较次数和移动次数约为n1.3当n趋于无穷时可减少到n(log2n)2交换排序(ExchangeSort)基本方法设待排序对象序列中的对象个数为n。一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字，如果发生逆序，则交换之，其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。基本思想是两两比较待排序对象的排序码,如发生逆序(即排列顺序与排序后的次序正好相反)，则交换之,直到所有对象都排好序为止。起泡排序(BubbleSort)210825492516214925251608214925251608214925251608214925251608214925251608起泡排序的过程起泡排序的算法typedefintSortData;voidBubbleSort(SortDataV[],intn){inti=1;intexchange=1;while(in&&exchange){exchange=0;//标志置为0,假定未交换for(intj=n-1;j=i;j--)if(V[j-1]V[j]){//逆序Swap(V[j-1],V[j]);//交换exchange=1;//标志置为1,有交换}i++;}}思考题：如何实现双起泡第i趟对待排序对象序列V[i-1],V[i],,V[n-1]进行排序,结果将该序列中排序码最小的对象交换到序列的第一个位置(i-1),其它对象也都向排序的最终位置移动。。最多做n-1趟起泡就能把所有对象排好序。在对象的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做n-1次排序码比较,不移动对象。这是最好的情形。最坏的情形是算法执行n-1趟起泡,第i趟(1in)做n-i次排序码比较,执行n-i次对象交换。这样在最坏情形下总的排序码比较次数KCN和对象移动次数RMN为：11111233121nininninRMNnninKCN)()()()(起泡排序是一个稳定的排序方法。快速排序(QuickSort)基本思想是任取待排序对象序列中的某个对象(例如取第一个对象)作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列：左侧子序列中所有对象的排序码都小于或等于基准对象的排序码右侧子序列中所有对象的排序码都大于基准对象的排序码基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。基准对象也称为枢轴（或支点）记录。QuickSort(List){if(List的长度大于1){将序列List划分为两个子序列LeftList和RightList;QuickSort(LeftList);QuickSort(RightList);将两个子序列LeftList和RightList合并为一个序列List;}}快速排序算法描述快速排序的过程2108254925*16初始关键字08254925*162108254925*1608254925*1608254925*1608254925*1621prikey一次交换二次交换三次交换四次交换完成一趟排序ijijjiijjiji08254925*1621完成一趟排序分别进行快速排序08254925*1621有序序列08254925*1621快速排序的算法voidQuickSort(SqList&L,intlow,inthigh){//在序列lowhigh中递归地进行快速排序if(lowhigh){intpivotloc=Partition(L,low,high);//划分QuickSort(L,low,pivotloc-1);//对左序列同样处理QuickSort(L,pivotloc+1,high);//对右序列同样处理}}intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];//子表的第一个记录作基准对象pivotkey=L.r[low].key;//基准对象关键字While(lowhigh){While(lowhigh&&L.r[high].key=pivotkey)--high;L.r[low]=L.r[high];//小于基准对象的移到区间的左侧While(lowhigh&&L.r[low].key=pivotkey)++low;L.r[high]=L.r[low];//大于基准对象的移到区间的右侧}L.