数据结构复习第八章

1、在复习时对每一种算法要从以下几个方面进行总结：1. 稳定性：稳定的算法是指经过排序之后，能使值相同的数据保持原顺序中的相对位置不变。时间复杂度：空间复杂度、最好两种情况各自适合什么时候使用：即什么时候最好，什么时候关。排序算法分几大类，每一类中又有几种。给出实例时，会排序。会写算法程序。，什么样的算法和初始状态无一（一） 直接排序：排序：它是一种稳定的排序方法。时间复杂度：（1）（2）最好情况：总共比较次数为 n-1，总共移动次数为 0，时间复杂度是 O(n)。情况：总共比较次数为(n+2)(n-1)/2，总共移动次数为(n-1)(n+4)/2，时间复杂度是 O()。（3）平均：总共比较次数为

2、，总共移动次数为，时间复杂度是 o()。3. 空间复杂度是 O(1)，哨兵作用：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。4. 当待排序列中的基本有序或待排序较少时，它是最佳的排序方法。5. 直接排序的效率与初始状态有关。void InsertionSort( SqList &L )i = 0;j = 0;for( i = 2 ; i = L.length ; i+ )if( L.ri.key L.ri-1.key )L.r0 = L.ri;for( j=i-1 ; L.r0.key =1)d handler code hereSInsert( L , k );k = k

3、/2;Display();void SInsert( SqList &L ,i = 0;j = 0;d )for( i = d + 1 ; i = L.length ; i+ )if( L.ri.key 0 ) & ( L.r0.key L.rj.key ) ; j-=d ) L.rj+d = L.rj;L.rj+d = L.r0;Display();二交换排序：（一） 冒泡排序：1. 它是一种稳定的排序方法。2. 时间复杂度：O()。（1） 最好情况：总共比较次数为 n-1，不移动。（2）情况：总共比较次数 n(n-1)/2，作等量级的移动。空间复杂度：O(适用于待排)。基本有序，或待排数目

4、较少的场合。5. 冒泡排序的效率和初始状态有关。void BubbleSort( SqList &L )/ TODO: Add your tag = 1 ;bound = L.length ; i = 0 ;j = 0 ;while(tag=1)tag=0; for(j=1;j L.rj+1.key )L.r0 = L.rj+1 ;L.rj+1 = L.rj ;L.rj = L.r0 ;tag = 1 ;bound-;Display();（二） 快速排序：它是一种不稳定的排序方法。时间复杂度：（1）最好情况：时间复杂度为 O()。（2）（3）情况：时间复杂度为 O(平均时间复杂度：时间复杂度是

5、 O()。)。3.空间复杂度：o(n)。4.适用于待排序个数很大且原始随机排序的情况，其平均性能是所有内排序算法中最好的一种。在最好每次能划分得到两个长度相等的子文件。在利于发挥长处。5.快速排序的效率和初始状态有关。6./4.快速排序void QuickSort( SqList &L )已基本有序最不/ TODO: Add your/*d handler code here首先，设 low 和 high 两个参数，分别指向首尾。然后，想怎样进行循环，怎样停止：怎样循环，先进行一次排序（这就是一个调用函数），利用它产生一个枢轴位置 p，然后两个递归函数，分别含两个参数（low/high,p）。

6、第一个左递归函数：low1=low , high1=p-1 ；第二个右递归函数：low2=p+1 , high2=high怎样停止：两侧的循环同时进行当每次循环时初始的 low 和 high 相同时，就终止。接着，思考怎样排序，排序函数参数有两个，low 和 high。while(lowhigh)while ( low= rlow.key ) high-;if(lowhigh)r0=rlow , rlow=rhigh , rhigh=r0 , low+;while ( lowhigh & rlow.key = rhigh.key ) low+;if(lowhigh)r0=rhigh , rhi

7、gh=rlow , rlow=r0 , high-;return low;*/Qsort( L,1,L.length ); Display();Partition( SqList &L ,low ,high )while(lowhigh)while ( low= L.rlow.key )high-; if(lowhigh)L.r0=L.rlow , L.rlow=L.rhigh , L.rhigh=L.r0 , low+;while ( lowhigh & L.rlow.key = L.rhigh.key ) low+;if(lowhigh)L.r0=L.rhigh , L.rhigh=L.r

8、low , L.rlow=L.r0 , high-;return low;void Qsort( SqList &L ,low ,high )pivotif(lowhigh)pivot= 0 ;= Partition( L , low , high );Qsort( L , low , pivot-1 );Qsort( L , pivot+1 , high );三选择排序：（一） 简单选择排序：1. 它是一种不稳定的排序方法。时间复杂度：O()空间复杂度：O(1)4. 适用于待排数目较少的场合。5. 简单排序的比较次数和/5.简单选择排序void SelectionSort( SqList &

9、L )/ TODO: Add your i = 0;j = 0;k = 0;初始状态无关。d handler code herefor( i = 1 ; i L.length ; i+ )k = i;for( j = i + 1 ; j = L.length ; j+ ) if( L.rj.key 0; i- )函数 2(L,i,L.length) for( j = L.length ; j 1 ; j- )交换 r1和 rj;函数 2(L,1,L.length);*/i = 0 ;high = 0;for( i = L.length/2 ; i 0 ; i- ) HeapAdjust( L,

10、i,L.length );for( high = L.length ; high 1 ; -high )L.r0 = L.r1;L.r1 = L.rhigh;L.rhigh = L.r0; HeapAdjust(L,1,high-1);Display();void HeapAdjust(SqList &L ,low ,high )i = 0 ;RedType temp ; L.r0 = L.rlow;for(i=2*low;i=high;i*=2)if(ihigh)&(L.ri.key = L.ri.key )break;elseL.rlow = L.ri; low = i ;L.rlow =

11、 L.r0;/四归并排序：（一） 二路归并排序：1.它是一种稳定的排序方法。时间复杂度：O(空间复杂度：O(n)4. 适用于待排数目较多时。5. 归并排序的比较次数和的初始状态无关。/7.二路归并排序void Merge( SqList &L ,k1 = 0;k2 = 0;i = 0;j = 0;low ,mid ,high )RedType* array = new RedTypehigh-low+1;k1 = low; k2 = mid+1;while(!(k1 mid|k2 high)if( L.rk1.key L.rk2.key )arrayi = L.rk1; k1+;i+;else

12、arrayi = L.rk2; k2+;i+;if( k1=mid )while( k1 = mid )arrayi = L.rk1; k1+;i+;if( k2=high )while( k2 = high )arrayi = L.rk2; k2+;i+;i=0;j=low; while(i=high-low)L.rj = arrayi; i+;j+;delete array;void MergeSort( SqList &L ,/ TODO: Add your/*思路：归并排序分成两步：low ,high )d handler code here利用递归进行划分：mid = (low+hi

13、gh)/2左半边：MergeSort(L,low,mid); 右半边：MergeSort(L,mid+1,high);进行归并：开辟一个动态数组 arrayhigh-low+1,对low,midmid+1,high两部分进行比较，因为是递归操作，所以每一部分一定是有序的采用交叉比较的方式进行排序，赋值到 arrayhigh-low+1中，然后再将排好序的序列返赋值回原数组。*/mid = 0; if(lowhigh)mid = (low+high)/2; MergeSort(L,low,mid); MergeSort(L,mid+1,high); Merge(L,low,mid,high);D

14、isplay();void MSort(SqList &L)MergeSort( L,1,L.length );Display();各种排序方法性能比较类型排序方法平均时间复杂度最好时间复杂度时间复杂度辅助空间复杂度稳定性排序直接排序稳定排序不稳定交换排序冒泡排序稳定快速排序不稳定选择排序简单选择排序稳定堆排序不稳定归并排序二路归并排序稳定总结一时间复杂度：时间复杂度：直接排序、冒泡排序、简单选择排序。其中以直接排序最常用，特别是对于关键字基本有序的序列。时间复杂度：快速排序、堆排序、归并排序。其中快速排序最快；在待排记录个数较多的情况下，归并排序比堆排序更快。时间复杂度介于和之间：排序。情况对直接选择排序、堆排序和归并排序影响并不大。在最好情况下，直接排序和冒泡排序最快；在平均情况下，快速排序最快；在情况下，堆排序和归并排序最快。二空间复杂度：空间复杂度：归并排序。空间复杂度：快速排序。空间复杂度：直接排序、排序、冒泡排序、简单选择排序、堆排序。三待排序数 n：越小，采用简单排序方法越合适； 越大，采用改进的排序方法越合适。四排序方法的选择：当待排个数 n 较