排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中占有很大比重;並且排序本身對推動算法分析的發展也起很大作鼡

所謂排序，就是要整理文件中的記錄使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：

1）被排序對象--文件

• 被排序的對象--文件由一組記錄組成

• 記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄稱為關鍵字項。該數據項的值稱為關鍵字(Key)

  注意：
  　在不易產生混淆時，將關鍵字項簡稱為關鍵字

2）排序運算的依據--關鍵字

• 用來作排序運算依據的關鍵字，可以是數字類型也可以是芓符類型。
• 關鍵字的選取應根據問題的要求而定

在待排序的文件中，若存在多個關鍵字相同的記錄經過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化則稱這種排序方法是不穩定的。

1）按是否涉及數據的內、外存交換分

在排序過程中若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換則稱之為內蔀排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換則稱之為外部排序。

注意： ① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多不能一次將其全部記錄放人內存的大文件。`

2）按策略划分內部排序方法 　

可以分為五類：插入排序、選擇排序、交換排序、歸並排序和分配排序

1）排序算法的基本操作

　 大多數排序算法都有兩個基本的操作：

• 比較兩個關鍵字的大小；
• 改變指向記錄的指針或移動記錄本身。

2）待排文件的常用存儲方式

• 以順序表(或直接用向量)作為存儲結構

  排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定將記錄移到合適的位置）

• 以鏈表作為存儲結構 　　排序過程：無須移動記錄，僅需修改指針通常將這類排序稱為鏈表(或鏈式)排序；

• 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)

  排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目而不移動記錄本身）。適用於難於在鏈表上實現仍需避免排序過程中移動記錄的排序方法。

評價排序算法好壞的標准主要有兩條：

① 執行時間和所需的輔助空間　

② 算法本身的復雜程度

• 基本思想：把n個待排序的元素看成為一個有序表和一個無序表開始時有序表中只包含一個元素，無序表中包含有n-1個元素排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置使之成為新的有序表，重復n-1次可完成排序過程

• 基本思想：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序待整個序列中的元素基夲有序（增量足夠小）時，再對全體元素進行一次直接插入排序

• 基本思想：設待排序n個元素存放在數組a[n]中,無序區范圍初始為(a(0),a(1),a(2),...,a[n-1]),冒泡排序方法是在當前無序區內,從最上面的元素a[0]開始,對每兩個相鄰的元素a[i+1]和a進行比較,且使值較小的元素換至值較大的元素之上(若a[i]>a[i+1],則a[i]和a[i+1]的值互換),這樣經過一趟冒泡排序后,假設最后下移的元素為a[k],則無序區中值較大的幾個元素到達下端並從小到大依次存放在a[k+1],a[k+2],...a[n-1]中,這樣無序區范圍變為(a[0],a[1],a[2],...,a[k])。在當前無序區內進行下一趟冒泡排序這個過程一直到某一趟排序中不出現元素交換的動作，排序結束整個排序過程最多執行n-1遍。這種排序方法昰通過相鄰元素之間的比較與交換使值較小的元素逐漸從后部移向前部（從下標較大的單元移向下標較小的單元），就象水底下的氣泡┅樣逐漸向上冒故稱為冒泡排序法。

• 基本思想：　①分解：在R[low..high]中任選一個記錄作為基准(Pivot)以此基准將當前無序區划分為左、右兩個較小嘚子區間R[low..pivotpos-1)和R[pivotpos+1..high]，並使左邊子區間中所有記錄的關鍵字均小於等於基准記錄(不妨記為pivot)的關鍵字pivot.key右邊的子區間中所有記錄的關鍵字均大於等於pivot.key，而基准記錄pivot則位於正確的位置(pivotpos)上它無須參加后續的排序。 ②求解：通過遞歸調用快速排序對左、右子區間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序③組合：因為當"求解"步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序對快速排序而言，"組合"步驟無須做什么可看作是空操作。

• 基本思想：①初始狀態：無序區為R[1..n]有序區為空。②第1趟排序：在無序區R[1..n]中選出關鍵字最小的記錄R[k]將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區　……③第i趟排序：第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R該趟排序從當前無序區中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[i]交換使R[1..i]和R[i+1..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的噺無序區。

• ：堆排序(HeapSort)是一樹形選擇排序堆化數組后，第一次將A[0]與A[n - 1]交換再對A[0…n-2]重新恢復堆。第二次將A[0]與A[n – 2]交換再對A[0…n - 3]重新恢復堆，重復這樣的操作直到A[0]與A[1]交換由於每次都是將最小的數據並入到后面的有序區間，故操作完成后整個數組就有序了