（八）排序技術(shù)
排序即是將一個無序的序列整理成按值非遞減順序排列的有序序列。在這里，我們討論的是順序存儲的線性表的排序操作。
1．交換類排序法
交換類排序法，即是借助于數(shù)據(jù)元素之間的互相交換進行排序的方法。
1）冒泡排序法
冒泡排序法即是利用相鄰數(shù)據(jù)元素之間的交換逐步將線性表變成有序序列的操作方法。
操作過程如下：
從表頭開始掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小，若相鄰兩個元素中前一個元素的值比后一個元素的值大，將兩個元素位置進行交換，當(dāng)掃描完成一遍時，則序列中的元素被放置到序列的最后。
再繼續(xù)對序列從頭進行掃描，這一次掃描的長度是序列長度減1，因為的元素已經(jīng)就位了，采用與前相同的方法，兩兩之間進行比較，將次大數(shù)移到子序列的末尾。
按相同的方法繼續(xù)掃描，每次掃描的子序列的長度均比上一次減1，直至子序列的長度為1時，排序結(jié)束。
例如，有序列5、2、9、4、1、7、6，將該序列從小到大進行排列。
采用冒泡排序法，具體操作步驟如下：
序列長度n=7
掃描的次數(shù)，最多需要掃描n-1次，如果序列已經(jīng)就位，則掃描結(jié)束。測試是否已經(jīng)就位，可設(shè)置一個標(biāo)志，如果該次掃描沒有數(shù)據(jù)交換，則說明數(shù)據(jù)排序結(jié)束。
2）快速排序法
冒泡排序方法每次交換只能改變相鄰兩個元素之間的逆序，速度相對較慢。如果將兩個不相鄰的元素之間進行交換，可以消除多個逆序。
快速排序的方法是：
從線性表中選取一個元素，設(shè)為T，將線性表后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果將線性表分成兩個部分（稱為兩個子表），T插入到其分界線的位置處，這個過程稱為線性表的分割。對過對線性表的一次分割，就以T為分界線，將線性表分成前后兩個子表，且前面子表中的所有元素均不大于T，而后面的所有元素均不小于T。
再將前后兩個子表再進行相同的快速排序，將子表再進行分割，直到所有的子表均為空，則完成快速排序操作。
在快速排序過程中，隨著對各子表不斷的進行分割，劃分出的子表會越來越多，但一次又只能對一個子表進行分割處理，需要將暫時不用的子表記憶起來，這里可用棧來實現(xiàn)。
對某個子表進行分割后，可以將分割出的后一個子表的第一個元素與最后一個元素的位置壓入棧中，而繼續(xù)對前一個子表進行再分割；當(dāng)分割出的子表為空時，可以從棧中退出一個子表進行分割。
這個過程直到棧為空為止，說明所有子表為空，沒有子表再需分割，排序就完成。
2．插入類排序法
1）簡單插入排序
插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。
插入排序操作的思路：在線性表中，只包含第1個元素的子表，作為該有序表。從線性表的第2個元素開始直到最后一個元素，逐次將其中的每一個元素插入到前面的有序的子表中。
該方法與冒泡排序方法的效率相同，最壞的情況下需要n(n-1)/2次比較。
例如，有序列5、2、9、4、1、7、6，將該序列從小到大進行排列。
采用簡單插入排序法，具體操作步驟如下：
序列長度n=7
2）希爾排序法
希爾排序法的基本思想：
將整個無序序列分割成若干小的子序列分別進行插入排序。
子序列的分割方法：將相隔某個增量h的元素構(gòu)成一個子序列，在排序的過程中，逐次減小這個增量，最后當(dāng)h減小到1時，再進行一次插入排序操作，即完成排序。
增量序列一般取ht=n/2k(k=1,2,…,[log2n])，其中n為待排序序列的長度。
3．選擇類排序法
1）簡單選擇排序法
基本思路：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面，然后對后面的子表采用相同的方法，直到子表為空為止。
對于長度為n的序列，需要掃描n-1次，每一次掃描均找出剩余的子表中最小的元素，然后將該最小元素與子表的第一個元素進行交換。
例如，有序列5、2、9、4、1、7、6，將該序列從小到大進行排列。
采用簡單選擇排序法，具體操作步驟如下：
2）堆排序法
堆排序法屬于選擇類排序方法。
堆的定義：具有n個元素的序列（h1,h2,…,hn），當(dāng)且僅當(dāng)滿足時稱之為堆。
本節(jié)只討論滿足前者條件的堆。
由堆的定義看，堆頂元素（即第一個元素）必為項。
可以用一維數(shù)組或完全二叉樹來表示堆的結(jié)構(gòu)。
用完全二叉樹表示堆時，樹中所有非葉子結(jié)點值均不小于其左右子樹的根結(jié)點的值，因此堆頂（完全二叉樹的根結(jié)點）元素必須為序列的n個元素中的項。
例如，有序列5、2、9、4、1、7、6，將該序列從小到大進行排列。
利用堆排序法將該序列進行排序。
操作方式即：先將無序堆的根結(jié)點5與左右子樹的根結(jié)點2、9進行比較，5<9，將5與9進行交換；整后，對左右子樹進行堆調(diào)整，左子樹的根結(jié)點2小于其左葉子結(jié)點5，調(diào)整；右子樹的根結(jié)點5小于其左右子結(jié)點7和6，根據(jù)堆的要求，將5與7進行調(diào)整。
根據(jù)堆的定義，可以得到堆排序的方法：
（1）首先將一個無序序列建成堆
（2）然后將堆頂元素（序列中的項）與堆中最后一個元素交換（項應(yīng)該在序列的最后）。
二、本章應(yīng)考點撥
本章內(nèi)容在筆試中會出現(xiàn)5-6個題目，是公共基礎(chǔ)知識部分出題量比較多的一章，所占分值也比較大，約10分。