九章排序ppt課件

1、各趟排序結果各趟排序結果0 1 2 3 4 50 1 2 3 4 5 temp250 1 2 3 4 5 temp4925*0 1 2 3 4 50 1 2 3 4 5 temp160 1 2 3 4 5 temp0816490 1 2 3 4 50 1 2 3 4 5 temp0 1 2 3 4 5 temp完成2525*0 1 2 3 4 50 1 2 3 4 5 temp0 1 2 3 4 5 temp21 Vectorj = temp; 111122142221nininnniRMNnnniKCN/)()( ,/)(22 while ( Left = Right ) int middl

2、e = ( Left + Right )/2; if ( temp = Left; k- ) Vectork+1 = Vectork; VectorLeft = temp; 1122log1logninnin例：例：99,14,28,31,2,7,46,70,62,180,30,82,170,5,90 1 2 3 4 5492516084925*0821252125*160 1 2 3 4 5491625*0821250 1 2 3 4 5序序 for ( int j = i; j = gap; j -= gap ) if ( temp Vectorj-gap ) Vectorj = Vect

3、orj-gap; else break; Vectorj = temp; gap = ( int ) ( gap / 2 ); 0 1 2 3 4 50 1 2 3 4 5 Swap ( Vectorj-1, Vectorj ); /交換 exchange = 1; /標志置為1,有交換 pass+; 11111233121nininninRMNnninKCN)()()()(直到一切的對象都排在相應位置上為止直到一切的對象都排在相應位置上為止。QuickSort ( List ) if ( List的長度大于的長度大于1) 將序列將序列List劃分為兩個子序列劃分為兩個子序列 LeftList

4、 和和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 將兩個子序列將兩個子序列 LeftList 和和 RightList 合并為一個序列合并為一個序列List; 快速排序的算法思想分治法分 難合并容易初始關鍵字：28 19 27 48 56 12 10 25 20 50完成第一趟后20 19 27 25 10 12 28 56 48 50完成第二趟12 19 10 20 25 27 28 50 48 56完成第三趟10 12 19 20 25 27 28 50 48 56int dataList : Partition

5、 (int s, int t ) int x, i, j; x=Vectors; i=s; j=t; while ( i j) while ( ( i =x) j=j-1; if (ij) ai=aj; while ( ( i j) & (Vectori=x) i=i+1; if (ij) aj=ai; Vectori =x; return i;序方法還要慢。序方法還要慢。2121211nnninni)()(0 1 2 3 4 5最小者最小者 08交換交換21,08最小者最小者 16交換交換25,16最小者最小者 21交換交換49,210 1 2 3 4 5結果結果最小者最小者 25*無交換無

6、交換最小者最小者 25無交換無交換各趟排序后的結果各趟排序后的結果012345025431012345025431template void MaxHeap :FilterDown ( const int i, const int EndOfHeap ) int current = i; int child = 2*i+1; Type temp = heapi; while ( child = EndOfHeap ) /最后位置最后位置 if ( child +1 EndOfHeap & heapchild = heapchild ) break; /temp排序碼大排序碼大, 不做調整不做調

7、整 else heapcurrent = heapchild; /大子女上移 current = child; /向下繼續(xù)調整 child = 2*child+1; heapcurrent = temp; /回放到適宜位置012345025431012345025431012345025431012345025431012345025431 mergedList.Vectork = Vectori; i+; k+; else mergedList.Vectork = Vectorj; j+; k+; if ( i = mid ) for ( int n1 = k, n2 = i; n2 = m

8、id; n1+, n2+ ) mergedList.Vectorn1 = Vectorn2; else for ( int n1 = k, n2 = j; n2 = right; n1+, n2+) mergedList.Vectorn1 = Vectorn2;template void datalist :MergePass ( dataList & mergedList, const int len ) int i = 0; while (i+2*len = CurrentSize-1) merge(mergedList, i, i+len-1, i+2*len-1); i += 2 * len; /循環(huán)兩兩歸并循環(huán)兩兩歸并 if ( i+len = CurrentS