1、1Agendav名次排序v選擇排序v冒泡排序v插入排序v基數排序v堆排序v歸并排序v快速排序21 1、名次排序、名次排序元素在隊列中的名次(rank)可定義為隊列中所有比它小的元素數目加上在它左邊出現的與它相同的元素數目。例如，給定一個數組a=4, 3, 9, 3, 7作為隊列，則各元素的名次為r=2,0,4,1,3。31 1、名次排序、名次排序template void Rank(T a, int n, int r) /計算a 0:n-1中n個元素的排名for (int i = 0; i n; i+)ri = 0; /初始化/逐對比較所有的元素for (int i = 1; i n; i+)

2、for ( int j = 0; j i; j+)if (a j = ai) ri+;else rj+;41 1、名次排序、名次排序template void Rearrange (T * &a, int n, int r) /按序重排數組a中的元素，使用附加數組uT *u = new Tn+1;/在u中移動到正確的位置for ( int i = 0; i n; i+)uri = ai;delete a;a=u;5根據a的元素之間所進行的比較操作來估算程序的時間復雜性。對于i的每個取值，執行比較的次數為i,所以總的比較次數為1+2+3+ +n-1 = (n-1)n/2。移動操作次數為：

3、n1 1、名次排序、名次排序62 2、選擇排序、選擇排序v思想：首先找出最大的元素，把它移動到an-1，然后在余下的n-1個元素中尋找最大的元素并把它移動到an-2，如此進行下去。7templateint Max(T a, int n)/ 尋找a 0 : n-1中的最大元素int pos = 0;for (int i = 1; i n; i+)if (apos ai)pos = i;return pos;每次調用Max(a,size)需要執行size-1次比較。2 2、選擇排序、選擇排序82 2、選擇排序、選擇排序template void SelectionSort (T a, int n)

4、 /對數組a 0:n-1中的n個元素進行排序for ( int size = n; size 1; size- -) int j= Max(a, size); /size-1次比較Swap( aj,asize-1 ) ; /移動3次9按照元素的比較次數來估算函數的時間復雜性。每次調用Max(a,size)需要執行size-1次比較，所以總的比較次數為：1+2+3+n-1= (n-1)n/2。移動次數為：3（n-1）2 2、選擇排序、選擇排序10上述程序中選擇排序函數的一個缺點是：即使元素已經按序排列，程序仍然繼續運行。為了終止不必要的循環，在查找最大元素期間，可以順便檢查數組是否已按序排列。2

5、 2、選擇排序、選擇排序11templatevoid SelectionSort(T a, int n)/ 及時終止的選擇排序bool sorted = false;for(int size = n; !sorted & (size 1);size-) int pos = 0;sorted = true;/ 找最大元素for (int i = 1; i size; i+)if (apos = ai) pos = i;else sorted = false; / 未按序排列Swap(apos, asize - 1 ) ; 2 2、選擇排序、選擇排序12v最好情況：數組a有序。v最壞情況：

6、數組a最大元素在首位，其他元素已經有序。 最好 最壞比較 n-1 n(n-1)/2移動 3 3(n-1)2 2、選擇排序、選擇排序133 3、冒泡排序、冒泡排序采用一種“冒泡策略”把最大元素移到右部。在冒泡過程中，對相鄰的元素進行比較，如果左邊的元素大于右邊的元素，則交換這兩個元素。在一次冒泡過程結束后，可以確信最大的元素肯定在最右邊的位置上。例: 11，15 ,3 ,9，20，7 ,1 ，在第一次冒泡過程結束后，得到？143 3、冒泡排序、冒泡排序template void Bubble (T a, int n) /把數組a0:n-1中最大的元素通過冒泡移到右邊for ( int i = 0

7、; i ai+1) Swap(ai,ai+1);153 3、冒泡排序、冒泡排序template void BubbleSort (T a, int n)/對數組a0:n-1中的n個元素進行冒泡排序for ( int i = n; i1; i- -)Bubble(a,i) ;163 3、冒泡排序、冒泡排序如果在一次冒泡過程中沒有發生元素互換，則說明數組已經按序排列，沒有必要再繼續進行冒泡過程。173 3、冒泡排序、冒泡排序templatebool Bubble(T a, int n) /把a0:n-1 中最大元素冒泡至右端bool swapped = false; / 尚未發生交換for (in

8、t i = 0; i ai+1) Swap(ai, ai+1);swapped = true; / 發生了交換return swapped;183 3、冒泡排序、冒泡排序templatevoid BubbleSort(T a, int n)/ 及時終止的冒泡排序for(int i = n;i1 & Bubble(a,i);i- -) ;最壞情況下比較次數，移動次數 ?最好情況下比較次數，移動次數 ?193 3、冒泡排序、冒泡排序v最好情況：數組a最初已經有序。v最壞情況：數組a倒序。最好 最壞v比較 n-1 n(n-1)/2v移動 0 3*n(n-1)/2204 4、插入排序、插入排序

9、v算法設計： 5, 2, 4, 10, 7 5, 2, 5, 2, 4, 5, 2, 4, 5, 10, 2, 4, 5, 7, 10214 4、插入排序、插入排序v思想：因為只有一個元素的數組是一個有序數組，所以可以從包含n個元素的數組的第一個元素開始。通過把第二個元素插入到這個單元數組中，可以得到一個大小為2的有序數組。插入第三個元素可以得到一個大小為3的有序數組。v按照這種方法繼續進行下去，最終將得到一個大小為n的有序數組。224 4、插入排序、插入排序templatevoid InsertionSort(T a, int n)for (int i=1; i = 0 & taj;

10、 j-)aj+1=aj;aj+1=t; 234 4、插入排序、插入排序v最好情況：數組a最初已經有序。v最壞情況：數組a倒序。 最好 最壞v比較 n-1 n(n-1)/2v移動 n-1 n-1+n(n-1)/2245 5、基數排序、基數排序一種更快的排序方法為箱子排序（bin sort）。在箱子排序過程中，節點首先被放入箱子之中，具有相同分數的節點都放在同一個箱子中，然后通過把箱子鏈接起來就可以創建一個有序的鏈表。255 5、基數排序、基數排序265 5、基數排序、基數排序voidBinSort(Chain& X, int range)/按分數排序intlen=X.Length();

11、Node x; Chain *bin;bin=new Chainrange+1;/分配到每個箱子中for(inti=1;i=0;j-)while(!binj.IsEmpty()binj.Delete(1,x);X.Insert(0,x);deletebin;275 5、基數排序、基數排序v在兩個for循環中執行的每一次插入和刪除操作所需要的時間均為(1)v因此第一個for循環的的復雜性為(n)，其中n為輸入鏈表的長度v第二個for循環的復雜性為(n+range)v因此函數BinSort總的復雜性為(n+range)(如果成功的話)。285 5、基數排序、基數排序v假定對范圍在0999之間的10

12、個整數進行排序。v如果使用range=1000來調用BinSort，那么箱子的初始化將需要1000個執行步，節點分配需要10個執行步，從箱子中收集節點需要1000個執行步，總的執行步數為2010。295 5、基數排序、基數排序v不直接對這些數進行排序，而是采用一些基數r來分解這些數。v在基數排序（radix sort）中，把數按照某種基數分解為數字，然后對數字進行排序。v基數r=箱子個數305 5、基數排序、基數排序315 5、基數排序、基數排序v對于一般的基數r，相應的分解式為： x%r;(x%r2)/r;(x%r3)/r2;.v當使用基數r=n對n個介于0nc-1范圍內的整數進行分解時，每

13、個數將可以分解出c個數字。v因此，可以采用c次箱子排序，每次排序時取range=n。整個排序所需要的時間為(cn)= (n)（因為c是一個常量）。326 6、堆排序、堆排序先將要排序的n 個元素初始化為一個最大堆，然后每次從堆中提取（即刪除）元素。各元素將按遞減次序排列。初始化所需要的時間為(n)，每次刪除所需要的時間為O(logn) ，因此總時間為O(nlogn) 。336 6、堆排序、堆排序template void HeapSort(T a, int n)/ 利用堆排序算法對a1:n 進行排序/ 創建一個最大堆MaxHeap H(1); H.Initialize(a,n,n) ;/ 從最大堆中逐個抽取元素T x;for (int i = n-1; i = 1; i-) H.DeleteMax(x) ;ai+1 = x;/ 在堆的析構函數中保存數組aH.Deactivate(x) ;346