1.1.7 排序技術

在排序技術方面，主要考查插入排序、選擇排序、冒泡排序、快速排序和堆排序等方法。

1.插入排序

每次將一個待排序的數(shù)據(jù)元素插入到前面已經(jīng)排好序的數(shù)列中的適當位置，使數(shù)列依然有序，直到待排序數(shù)據(jù)元素全部插入完為止。

例，使用插入排序對3、4、2、1、5按照從小到大的順序排序。

排序過程分析：

2.選擇排序

每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(shù)列的最前，直到全部待排序的數(shù)據(jù)元素排完。

例，使用選擇排序對3、4、2、1、5按照從小到大的順序排序。

排序過程分析：

3.冒泡排序

兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時即進行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。

設想被排序的數(shù)組R[1..N]垂直豎立，將每個數(shù)據(jù)元素看成有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”，如此反復進行，直至最后任何兩個氣泡都是輕者在上、重者在下為止。

例，使用冒泡排序對3、4、2、1、5按照從小到大的順序排序。

排序過程分析：

4.快速排序

在當前無序區(qū)R[1..H]中任取一個數(shù)據(jù)元素作為比較的“基準”（不妨記為X），用此基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H]（1≤I≤H），當R[1..I-1]和R[I+1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。

例如，使用快速排序對7、8、3、4、9、1進行從小到大的排序（僅寫出第一趟的結果，以第一個元素為主）。

排序過程分析：

一般來說，在考試的時候，只問第一趟的結果，也就是以第一個元素為主排列的結果。

5.堆排序

堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親節(jié)點和孩子節(jié)點之間的內(nèi)在關系來選擇最小的元素。

N個元素的序列K1,K2,K3,…,KN稱為堆，當且僅當該序列滿足以下特性：

Ki≤K2i，Ki≤K2i+1（1≤i≤[N/2]）

堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子節(jié)點的關鍵字均大于等于其孩子節(jié)點的關鍵字。

堆排序正是利用小根堆（或大根堆）來選取當前無序區(qū)中關鍵字最小（或最大）的記錄實現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當前無序區(qū)調(diào)整為一個大根堆，選取關鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴大到整個記錄區(qū)。

例如，使用堆排序對7、8、3、4、9、1進行從小到大的排序，僅寫出第一趟排序的結果。

排序過程分析：

因為有6個數(shù)，首先取6/2=3，然后看看k3≤k6是否成立（此處沒有k7），因為k3的值是3，而k6的值是1，顯然不滿足條件，要將k3和k6進行交換，就變成如下形式：

然后再看k2≤k4和k2≤k5是否成立。因為k2的值是8，k4的值是4，而k5的值是9，所以，將k2的值和k4的值交換，得到如下序列：

再看k1≤k2和k1≤k3，發(fā)現(xiàn)不滿足，此時的k1要和k2與k3中最小的一個進行交換，所以得到序列如下：

堆建好了嗎？檢查每個位置是否滿足上面的條件，答案是“沒有”。因為此時k3≤k6又不成立了，所以要進行交換，得到如下的序列：

以上是第一趟排列的結果，如果要進行第二趟堆排序的話，就從剩下的4、3、8、9、7開始。

6.各種排序方法的比較

各種排序方法的比較如表1-1所示。

表1-1 各種排序算法的比較