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