1、在復(fù)習(xí)時(shí)對(duì)每一種算法要從以下幾個(gè)方面進(jìn)行總結(jié)：1. 穩(wěn)定性：穩(wěn)定的算法是指經(jīng)過(guò)排序之后，能使值相同的數(shù)據(jù)保持原順序中的相對(duì)位置不變。時(shí)間復(fù)雜度：空間復(fù)雜度、最好兩種情況各自適合什么時(shí)候使用：即什么時(shí)候最好，什么時(shí)候關(guān)。排序算法分幾大類(lèi)，每一類(lèi)中又有幾種。給出實(shí)例時(shí)，會(huì)排序。會(huì)寫(xiě)算法程序。，什么樣的算法和初始狀態(tài)無(wú)一（一） 直接排序：排序：它是一種穩(wěn)定的排序方法。時(shí)間復(fù)雜度：（1）（2）最好情況：總共比較次數(shù)為 n-1，總共移動(dòng)次數(shù)為 0，時(shí)間復(fù)雜度是 O(n)。情況：總共比較次數(shù)為(n+2)(n-1)/2，總共移動(dòng)次數(shù)為(n-1)(n+4)/2，時(shí)間復(fù)雜度是 O()。（3）平均：總共比較次數(shù)為

2、，總共移動(dòng)次數(shù)為，時(shí)間復(fù)雜度是 o()。3. 空間復(fù)雜度是 O(1)，哨兵作用：免去查找過(guò)程中每一步都要檢測(cè)整個(gè)表是否查找完畢，提高了查找效率。4. 當(dāng)待排序列中的基本有序或待排序較少時(shí)，它是最佳的排序方法。5. 直接排序的效率與初始狀態(tài)有關(guān)。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. 它是一種穩(wěn)定的排序方法。2. 時(shí)間復(fù)雜度：O()。（1） 最好情況：總共比較次數(shù)為 n-1，不移動(dòng)。（2）情況：總共比較次數(shù) n(n-1)/2，作等量級(jí)的移動(dòng)。空間復(fù)雜度：O(適用于待排)?；居行?，或待排數(shù)目

4、較少的場(chǎng)合。5. 冒泡排序的效率和初始狀態(tài)有關(guān)。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();（二） 快速排序：它是一種不穩(wěn)定的排序方法。時(shí)間復(fù)雜度：（1）最好情況：時(shí)間復(fù)雜度為 O()。（2）（3）情況：時(shí)間復(fù)雜度為 O(平均時(shí)間復(fù)雜度：時(shí)間復(fù)雜度是

5、 O()。)。3.空間復(fù)雜度：o(n)。4.適用于待排序個(gè)數(shù)很大且原始隨機(jī)排序的情況，其平均性能是所有內(nèi)排序算法中最好的一種。在最好每次能劃分得到兩個(gè)長(zhǎng)度相等的子文件。在利于發(fā)揮長(zhǎng)處。5.快速排序的效率和初始狀態(tài)有關(guān)。6./4.快速排序void QuickSort( SqList &L )已基本有序最不/ TODO: Add your/*d handler code here首先，設(shè) low 和 high 兩個(gè)參數(shù)，分別指向首尾。然后，想怎樣進(jìn)行循環(huán)，怎樣停止：怎樣循環(huán)，先進(jìn)行一次排序（這就是一個(gè)調(diào)用函數(shù)），利用它產(chǎn)生一個(gè)樞軸位置 p，然后兩個(gè)遞歸函數(shù)，分別含兩個(gè)參數(shù)（low/high,p）。

6、第一個(gè)左遞歸函數(shù)：low1=low , high1=p-1 ；第二個(gè)右遞歸函數(shù)：low2=p+1 , high2=high怎樣停止：兩側(cè)的循環(huán)同時(shí)進(jìn)行當(dāng)每次循環(huán)時(shí)初始的 low 和 high 相同時(shí)，就終止。接著，思考怎樣排序，排序函數(shù)參數(shù)有兩個(gè)，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 );三選擇排序：（一） 簡(jiǎn)單選擇排序：1. 它是一種不穩(wěn)定的排序方法。時(shí)間復(fù)雜度：O()空間復(fù)雜度：O(1)4. 適用于待排數(shù)目較少的場(chǎng)合。5. 簡(jiǎn)單排序的比較次數(shù)和/5.簡(jiǎn)單選擇排序void SelectionSort( SqList &

9、L )/ TODO: Add your i = 0;j = 0;k = 0;初始狀態(tài)無(wú)關(guān)。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- )函數(shù) 2(L,i,L.length) for( j = L.length ; j 1 ; j- )交換 r1和 rj;函數(shù) 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.它是一種穩(wěn)定的排序方法。時(shí)間復(fù)雜度：O(空間復(fù)雜度：O(n)4. 適用于待排數(shù)目較多時(shí)。5. 歸并排序的比較次數(shù)和的初始狀態(tài)無(wú)關(guān)。/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利用遞歸進(jìn)行劃分：mid = (low+hi

13、gh)/2左半邊：MergeSort(L,low,mid); 右半邊：MergeSort(L,mid+1,high);進(jìn)行歸并：開(kāi)辟一個(gè)動(dòng)態(tài)數(shù)組 arrayhigh-low+1,對(duì)low,midmid+1,high兩部分進(jìn)行比較，因?yàn)槭沁f歸操作，所以每一部分一定是有序的采用交叉比較的方式進(jìn)行排序，賦值到 arrayhigh-low+1中，然后再將排好序的序列返賦值回原數(shù)組。*/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();各種排序方法性能比較類(lèi)型排序方法平均時(shí)間復(fù)雜度最好時(shí)間復(fù)雜度時(shí)間復(fù)雜度輔助空間復(fù)雜度穩(wěn)定性排序直接排序穩(wěn)定排序不穩(wěn)定交換排序冒泡排序穩(wěn)定快速排序不穩(wěn)定選擇排序簡(jiǎn)單選擇排序穩(wěn)定堆排序不穩(wěn)定歸并排序二路歸并排序穩(wěn)定總結(jié)一時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：直接排序、冒泡排序、簡(jiǎn)單選擇排序。其中以直接排序最常用，特別是對(duì)于關(guān)鍵字基本有序的序列。時(shí)間復(fù)雜度：快速排序、堆排序、歸并排序。其中快速排序最快；在待排記錄個(gè)數(shù)較多的情況下，歸并排序比堆排序更快。時(shí)間復(fù)雜度介于和之間：排序。情況對(duì)直接選擇排序、堆排序和歸并排序影響并不大。在最好情況下，直接排序和冒泡排序最快；在平均情況下，快速排序最快；在情況下，堆排序和歸并排序最快。二空間復(fù)雜度：空間復(fù)雜度：歸并排序?？臻g復(fù)雜度：快速排序?？臻g復(fù)雜度：直接排序、排序、冒泡排序、簡(jiǎn)單選擇排序、堆排序。三待排序數(shù) n：越小，采用簡(jiǎn)單排序方法越合適； 越大，采用改進(jìn)的排序方法越合適。四排序方法的選擇：當(dāng)待排個(gè)數(shù) n 較