Sorting algorithm Sorting by Counting 通過計數的方式來排序 Comparison Counting 假設對A[1...N]數組進行排序，用一個數組count[1...N]來統計每個數應該出現的位置， 1 Set count[1...N] = 0; 2 for i = N; i > 1; i-- 2 for j = i-1; j >=1; j--; if A[j] > A[i] count[j]++; else count[i]++; 例如對於數組2 3 4 1 5 第一次統計後count為：0 0 0 0 4 第二次統計後count為：1 1 1 0 4 第三次統計後count為：1 1 3 0 4 第四次統計後count為：1 2 3 0 4 最後的count則對應了其出現的下標值 顯然該算法時間復雜度為O(n^2）空間復雜度為O(n)，很爛的算法，沒啥用處，不過不需要移動記錄 Distribution Counting 該方法是對上面方法的改進，假設數組A的最大值和最小值分別為min max，設置一個count[min...max]數組來統計每個數應該出現的位置 1 Set count[min...max] = 0; 2 for( i = 1; i <= N; i++) count[A[i] += 1; 3 for (i = min+1; i <= max; i++) count[i] = count[i] + count[i-1]; 該方法不需要進行任何比較操作，有點像後面要提到的Radix Sorting Sorting by Insertion 插入排序，該算法的基本思想和我們打撲克牌的時候插牌的方法類似，當我們要接到第i個牌的時候，我們手上的i-1個牌已經是有序的了，那麼我們找到合適的位置，把第i張牌插進去。 Straight insertion直接插入 for(i = 2; i <= N; i++) pivote = A[i]; for( j = i-1; j >= 1; j--) if (A[j] > A[i]) A[j+1] = A[j]; else break; A[j + 1] = pivote; 該算法最壞情況就是輸入數組為逆序的情況，則比較和移動的次數為1+2+...+N-1= N*(N-1)/2 O(n^2) 平均下來，對於i，每次比較和移動次數為i/2，則總的次數為N*(N-1)/4 約為(N^2)/4 該算法在N不是很大，且數組基本有序的情況下，可以獲得最好的效率，因此很多排序算法在對數據進行部分排序時，通常使用該算法。 Binary Insertion and two-way Insertion 對於第i個數，因為前i-1個數都是有序的了，我們需要找到合適的位置來將i插入進去，因此我們可以使用二分查找的方式在i-1中尋找合適的位置，例如對於i=64，則比較A[32]，如果大於A[64]則比較A[16]否則比較 A[48]，這樣查找相應的插入位置只需要log2N次比較。但是即使我們找到了合適的插入位置，我們仍然需要將後面的記錄往後挪一個位置，來騰出空間給要插入的數A[i]，因此總的時間復雜度並沒有降低。 Shell Sorting希爾排序 如果某個排序算法，一次只移動一個位置的話，那麼其時間復雜度是O(n)，因此如果我們要提高效率的話，那麼每次比較不能只是移動一個位置，而應該移動盡可能多的位置。希爾排序就是這樣的算法，也稱為Diminishing increment sortion 例如對於16條記錄，我們將其分為8組(A1,A9) (A2, A10)...(A8, A16)分別對每一組進行排序 之後分為4組A1, A5, A9, A 13)...(A4, A8, A12, A16)分別對每一組進行排序 然後分為2組，分別對每一組排序 最後對整個數組排序 對於每一個小組的排序可以使用直接插入排序。對於組的選取可以根據數據的不同來選取，但是最後一定是1，例如此處是8 4 2 1當然也可以劃分為7 5 3 1 等等。 //h is the group number ShellSort(array A, int N, int h) { for(i = 1; i < h; i++) for(j = i + h; j < N; j+=h) pivote = A[j]; for(k = j - h; k >0; k-=h) if (A[k] > A[j]) A[k+h] = A[k]; else break; A[k+h] = pivote; } //assume array h stores the group number Shell(array A, int N, array h, int g_num) { for(i = 1; i <= g_num; i++) ShellSort(A, N, h[i]); } shell排序最關鍵的就是分組數目的選取，我們可以想象，當分組為N的時候，該算法就退化成了直接插入排序算法。 理論上證明當數組hi = 2^i -1的時候，算法時間為N^(3/2) Sorting by Exchanging 交換排序的基本思想是交互一對out of order的數，直到待排序列中沒有out of order的對為止 直接插入排序也可以看成是交換排序：對於A[i]每次和它的鄰居比較，如果不是order，則交換，直到交換到合適的位置為止。 因此，插入、交換、選擇排序之間並沒有嚴格的區分。 交換排序主要有四種方式：Exchange selection(bubble sort冒泡法）merge exchage(歸並排序) partition exchange(快速排序) radix exchange(基數排序) bubble sort 最顯然的方法就是A1和A2比較，如果A1大，則交換，繼續比較A2 A3， A3 A4，一次下來之後，最大的元素則在最右邊。接下來對N-1個元素繼續這樣操作 for(i = 1; i < N; i++) { for(j = 1; j <= N-i; j++) { if(A[j] > A[j+1]) { exchange(A[j], A[j+1); } } } 此處給出的是最簡單的實現方法，顯然這個方法還有很多改進的地方，比如說不一定非要循環N-1次，如果某次循環的時候發現沒有進行交換了，則表明序列已經是順序的了，可以跳出，比如每次也不一定非要循環到N-i的地方，而是循環到上次最後一次做exchange操作的下標處就可以了，因為後面沒有再進行exchange，則表明後面已經是有序的了。 exchange_bound = N-1; is_exchange = 0; for(i = 1; i < N; i++) { for(j = 1; j <= exchange_bound; j++) { if(A[j] > A[j+1]) { exchange(A[j], A[j+1); is_exchage++; exchange_bound = j; } } if (is_exchange == 0) break; } QuickSort快速排序 快速排序的基本思想是通過partition，partition是從待排序列中選取某個值，然後按照這個值來進行劃分，左邊的數都小於這個值，右邊的數都大於這個值，然後對左邊和右邊的數繼續劃分。 partition(array, low, high) { if (array == NULL) return -1; if (low >= high) return low; pivote = array[low]; i = low; j = high; while( true) { while(array[j] >= pivote && i < j) j--; while(array[i] <= pivote && i < j) i++; if (i < j) exchange(array[i], array[j]; else { exchange(array[low], array[j]); return j; } } } 另一種實現方法是一頭查找 partition(array, low, high) { if (array == NULL) return -1; if (low >= high) return low; i = low - 1; j = low; while(j < high) { if (array[j] < array[high]) { i++; exchage(array[i], array[j]; } j++; } exchange(array[i+1], array[high]); return i+1; } quicksort(array, low, high) { if(array == NULL || low >= high) return; mid = partition(array, low, high); quicksort(array, low, mid -1); quicksort(array, mid+1, high); } 快速排序最壞情況下的時間復雜度需要O(n^2)，但是一般情況下，快速排序的時間復雜度為O(n*log2n)，在比較排序中，快速排序是性能最好的一種排序方式，另外也可以對其進行改進，當劃分後的子數組個數小於8個的時候，可以使用直接排序，而不必再進行劃分了。 Radix Exchanging sorting 基數交換排序 基數交換排序是利用每個數的二進制表示來進行排序的，同一般的比較不同，它是通過二進制相應的位為0或1來比較。它有點類似與快速排序，其過程是： 1、將序列按照最高位來劃分，左邊的數該位都為0，右邊的數該位都為1. 2、繼續對最高位為0的新序列按照下一位為0還是1繼續劃分，右邊序列也一樣，直到最後一位 這樣最終就得到了有序的序列了。 radixPartition(array, low, high, bit) { if (array == NULL) return -1; if (low >= high) return low; i = low; j = high; while(true) { while(array[j] &b && i < j) j--; while(!(array[i] &b) && i < j) i++; if (i < j) exchange(array[i], array[j]; else { return j; } } } radixSort(array, low, high, bit) { if(array == NULL || low >= high) return; mid = radixPartition(array, low, high, bit); bit = bit >> 1; radixSort(array, low, mid, bit); radixSort(array, mid+1, high, bit); } 基數排序的時間復雜度和快速排序一樣，但是據說比快速排序要快一點。 Sorting By Selection 選擇排序 排序算法中另外一個比較重要的方式就是選擇，通過不斷的選擇來求得最終有序的序列，最簡單的方法一般是： 1、從序列中找到最小的數，輸出，將這個為止置為無窮大； 2、繼續步驟1 3、直到N個記錄都已經選取出來了 選擇排序要求所有待排列的數據都是已知的，其最終結果是一次一次累計產生出來的，而上面提到的其它排序方式，在排序中間我們始終是沒有辦法得到一個有序的序列，直到排序完成之後才最終得到有序的序列，而選擇排序則排序過程中生成的結果都已經是有序的了。 上面的方法每找到一個最小記錄需要N-1次比較，並且需要一個N個大小的空間來存儲最終的結果，顯然我們可以對其進行改進，不需要使用無窮大值，而只需要在每次找到一個最小值之後，將該值放置到原數組中合適的位置上就可以了。 Straight Selection Sort 直接選擇排序 StrainghtSort(array, low, high) { iMin = low; for (i = low; i < high; i++) iMin = i; for(j = i+1; j <= high; j++) if(array[j] < array[iMin) iMin = j; exchange(array[i], array[iMin); } 顯然該算法需要(N*(N-1))/2次比較。 該算法和bubble sort冒泡排序有點相似，但是冒泡排序一趟操作需要進行多次交換，而該算法一趟操作只需要一次交換。 那麼這個算法是否可以改進呢？比如尋找最小值是不是可以少比較幾次？ 研究表明，要從N個數中找到最大或者最小的值，至少需要N-1次比較。 但是這個定理只對第一次查找有效，如果能夠利用每次比較的結果的話，那麼第二次尋找最大或最小值就可以減少比較次數。 這就是tree selection的基本思想。 Tree Selection Tree Selection的基本思想就是通過兩兩比較的勝者建立一顆二叉樹，和比賽時選擇冠軍的方法一樣，如下圖所示 6 3 6 1 3 6 4 得到這棵樹之後，我們就可以把根節點輸出，這個是最大值，然後把其對應位置設置為最小值，然後將其所在的路徑重新計算，最終可以得到第二大的數，只需要Log2N次比較。 4 3 4 1 3 0 4 但是該算法需要額外的空間來存儲這棵樹，而且要使用負無窮大來替換輸出的元素，那麼有沒有好的辦法來解決這些問題呢？ Heapsort 堆排序 堆排序直接利用數組來存儲樹，對於節點i，其左右孩子分別為2*i和2*i+1，其父節點為i/2取下限。 對於一個數組中的元素，如果Ai < Ai*2 並且 Ai < Ai*2+1 那麼我們稱這是一個小頂堆，即根節點為最小的元素。 如果我們可以將一個數組轉換成一個堆，那麼我們就可以按照tree selection方法自頂向下得到一個有序的序列。 堆排序算法： 首先我們將一個數組轉換為一個堆，然後將堆頂元素挪到合適的為止，將剩余數組重新調整為新的堆，直到得到所有元素。 HeapAdjust(array, i, N) { l_child = 2*i; r_child = 2*i+1; largest = i; if (l_child <= N && array[l_child] > array[i]) largest = l_child; if (r_child <= N && array[r_child] > array[largest]) largest = r_child; if (largest != i) exchange(array[largest], array[i]); HeapAdjust(array, largest, N); } HeapSort(array, N) { for(i = N/2; i >=0; i--) HeapAdjust(array, i, N); for(i = N; i >1; i--) exchange(array[1], array[i]); HeapAdjust(array, 1, i-1); } 其時間復雜度為O(N*log2N)，對於N很大的情況，該算法效率還不錯，但是當N很小的時候，該算法性能並不好，因為第一次構建堆的時候是比較耗時的，後面查找元素調整堆都最多只需要進行h樹的高度）次比較就夠了 。 相比較快速排序，在最壞情況下，快速排序不如堆排序，堆排序的最壞情況和平均情況下性能差別不大，但是在平均情況下，快速排序則明顯優於堆排序。 但是堆排序有個比較有意思的現象就是Largest in, first out。因此堆排序可以用來實現優先級隊列Priority Queue)，例如操作系統按照進程的優先級調度，進程的優先級也許會不斷的發生變化，但是每次出隊的進程總會是優先級最高的。如果要實現優先級隊列，則除了上述操作之外，還需要加入修改，插入操作。 Sorting By Merging歸並排序 歸並的意思就是將兩個或多個已經有序的數組合並為一個有序的數組。 兩路歸並算法為： Merge(arraya, m, arrayb, n) { while(i <=m && j <=n) if(arraya[i] < arrayb[j]) newArray[k++] = arraya[i]; i++; else newArray[k++] = arrayb[j]; j++; while(i <= m) newArray[k++] = arraya[i]; while(j <= n) newArray[k++] = arrayb[j]; return newArray; } 顯然上述算法最多需要進行m+n次比較。 因此我們可以將一個數組不斷的劃分為多個小數組，對小數組進行排序後再歸並為一個大的數組，直到所有都歸並完成。另外我們也可以引入直接插入排序來對小數組先排序，然後向上歸並。 Sorting By Distribution分布排序 Radix Sorting 基數排序 基數排序是對待排序列中存在多個關鍵字的情況下進行排序，例如我們對撲克牌進行排序，撲克牌有花色和面值兩個關鍵字，那麼基數排序就是先按照優先級較小的關鍵字分成若干堆，然後把這些堆壘成一個堆，接著按照更高優先級來將這個堆化為新的N個堆，把這些堆繼續壘成一個堆，直到所有關鍵字都做完了，那麼最後的結果就是有序的了。 例如對於數組：329 457 657 839 436 720 355 我們可以認為它有三個關鍵字，分別是百位數，十位數和個位數，其中個位數優先級最低，百位數最高 首先對個位數分堆 720 355 436 457 329 657 839 0 5 6 7 9 合並起來就是：720 355 436 457 657 329 839 繼續對十位數分堆 720 436 355 329 839 457 657 2 3 5 合並起來就是：720 329 436 839 355 457 657 繼續對百位數分堆 329 436 657 720 839 355 457 3 4 6 7 8 合並起來就是：329 355 436 457 657 720 839 也就得到了一個有序的序列了 整個過程中不需要任何的比較操作，只要把每個數放入相應的堆就可以了。 假設有N個數，M個堆，那麼每個堆需要至少N個空間來保證可以容納下所有可能的數，這樣總的額外空間就需要(M+1)*N，這樣的開銷無論如何是無法承受的了。 之後對該算法進行了改進，只需要2N個空間和M個計數器，其原理是第一遍掃描先統計每個堆上的記錄數，這樣我們就確切的知道每個堆需要分配多少空間來容納這些記錄 因此，基數排序的基本算法就是： 使用優先級最小的關鍵字，將記錄移動到額外空間，然後使用更高一級的關鍵字，將記錄從額外空間移動到原始空間……直到所有關鍵字都統計完 而每一次移動需要三步操作：統計個數、分配空間、移動。 參考文獻： The Art of Computer Programming vol 3 Sorting and Searching Introduction to algorithm
