排序演演算法

在討論排序演演算法時，數據通常是指由若干記錄組成的文件，每個記錄包含一個或多個數據項。其中能夠標誌該記錄的數據項稱為鍵碼，給定一文件的n個記錄錄{R1,R2….Rn}及其相應的鍵碼集合{K1,K2…Kn}，所謂排序就是將記錄按鍵碼遞增次序排列起來，當待排序的文件能夠同時裝入計算機的主存中時，則相應的排序稱為內排序。如果文件大到不能同時全部裝入主存中而有一部分必須放在外存上時，則相應的排序稱為外排序。當待排序的文件中包含有一些相同鍵碼的記錄時，如果經過排序后這些相同鍵碼的記錄的相對次序仍然保持不變，則相應的排序演演算法是穩定的ꎬ否則為不穩定的。如果排序演演算法設計成單處理機完成的，則此排序演演算法稱為串列(或順序)排序演演算法，如果排序演演算法設計成多處理機實現的，則稱為并行排序演演算法。度量串列排序演演算法複雜度的標準是演演算法的運行時間和所佔用的存儲空間，度量并行排序演演算法複雜度的標準是演演算法的總運行時間和所需的處理器數。排序的應用很廣，在科學計算和數據處理中，在資料庫和知識庫管理系統中，在系統軟體和應用軟體中以及在高級計算機體系結構中，都會直接或間接地遇到大量的排序問題。排序在計算機科學研究中佔有相當的地位，人們已經發現，排序問題的研究方法和思路，演演算法的設計和分析技巧，對研究計算機諸多領域中其他問題的演演算法都頗值得借鑒。

排序演演算法最重要的幾個評估標準主要有以下幾方面：

（1）時間複雜度：即從序列的初始狀態到經過排序演演算法的變換移位等操作變到最終排序好的結果狀態的過程所花費的時間度量。

（2）空間複雜度：就是從序列的初始狀態經過排序移位變換的過程一直到最終的狀態所花費的空間開銷。

（3）使用場景：排序演演算法有很多，不同種類的排序演演算法適合不同種類的情景，可能有時候需要節省空間對時間要求沒那麼多，反之，有時候則是希望多考慮一些時間，對空間要求沒那麼高，總之一般都會必須從某一方面做出抉擇。

（4）穩定性：穩定性是不管考慮時間和空間必須要考慮的問題，往往也是非常重要的影響選擇的因素。

插入排序演演算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的後面，因此插入該元素后並未改變原序列的前後順序。我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。

冒泡排序演演算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和演演算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重複進行上述計算，直至完成第(n一1)個和第n個記錄的關鍵字之間的比較，此後，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴格的穩定排序演演算法，它不改變序列中相同元素之間的相對位置關係。

選擇排序演演算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置即可；以此類推，重複進行“最小元素”的選擇，直至完成第(n-1)個位置的元素選擇，則第廳個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同於冒泡法的細節。舉例說明：序列58539．我們知道第一遍選擇第1個元素“5”會和元素“3”交換，那麼原序列中的兩個相同元素“5”之間的前後相對順序就發生了改變。因此，我們說選擇排序不是穩定的排序演演算法，它在計算過程中會破壞穩定性。

快速排序的基本思想是：通過一趟排序演演算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分后的這兩塊序列的元素分別再次實行快速排序演演算法，排序實現的整個過程可以是遞歸的來進行調用，最終能夠實現將所需排序的無序序列元素變為一個有序的序列。

歸併排序演演算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規則進行排序為長序列。歸併排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合併得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列；將上述步驟重複操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該演演算法不會破壞序列的穩定性，即歸併排序也是穩定的排序演演算法。