考點(diǎn)8 排序技術(shù)

1.交換類排序法

交換類排序法是指借助數(shù)據(jù)元素的“交換”進(jìn)行排序的一種方法。本節(jié)介紹的冒泡排序法和快速排序法就是屬于交換類排序法。

（1）冒泡排序法。

冒泡排序的基本思想。

在線性表中依次查找相鄰的數(shù)據(jù)元素，將表中最大的元素不斷往后移動(dòng)，反復(fù)操作直到消除所有逆序。此時(shí)，該表已經(jīng)排序結(jié)束。

冒泡排序法的基本過程。

①從表頭開始往后查找線性表，在查找過程中逐次比較相鄰兩個(gè)元素的大小。若在相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們交換。

②從后向前查找剩下的線性表（除去最后一個(gè)元素），同樣，在查找過程中逐次比較相鄰兩個(gè)元素的大小。若在相鄰兩個(gè)元素中，后面的元素小于前面的元素，則將它們交換。

③對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，線性表排序完成。

假設(shè)線性表的長度為n，則在最壞的情況下，冒泡排序需要經(jīng)過n／2遍從前往后的掃描和n／2遍從后往前掃描，需要比較n（n-1）／2次，其數(shù)量級為n2。

（2）快速排序法。

快速排序法的基本思想。

在線性表中逐個(gè)選取元素，將線性表進(jìn)行分割，直到所有元素全部選取完畢，此時(shí)線性表已經(jīng)排序結(jié)束。

快速排序法的基本過程。

①從線性表中選取一個(gè)元素，設(shè)為T，將線性表后面小于T的元素移動(dòng)到前面，而將大于T的元素移到后面，這樣就將線性表分成了兩部分（稱為兩個(gè)子表）。T就是處于分界線的位置，將線性表分成了前后兩個(gè)子表，且前面子表中的所有元素均不大于T，而后子表中的所有元素均不小于T，此過程稱為線性表的分割。

②對分割后的子表再按上述原則進(jìn)行反復(fù)分割，直到所有子表為空為止，則此時(shí)的線性表就變成有序。

真考鏈接

考核概率為25%，考生需要掌握該考點(diǎn)內(nèi)容，主要是各種排序方法的概念、基本思想以及它們的復(fù)雜度。

2.插入類排序法

插入排序是指將無序序列中的各元素依次插入已經(jīng)有序的線性表中。本節(jié)將主要介紹簡單插入排序法和希爾排序法。

（1）簡單插入排序法。

簡單插入排序是把n個(gè)待排序的元素看成一個(gè)有序表和一個(gè)無序表，開始時(shí)，有序表只包含一個(gè)元素，而無序表包含n-1個(gè)元素，每次取無序表中的第一個(gè)元素插入到有序表中的正確位置，使之成為增加一個(gè)元素的新的有序表。插入元素時(shí)，插入位置及其后的記錄依次向后移動(dòng)。最后有序表的長度為n，而無序表為空，此時(shí)排序完成。

在簡單插入排序中，每一次比較后最多移除一個(gè)逆序，因此，該排序方法的效率與冒泡排序法相同。一般簡單插入排序需要n（n-1）／2次比較。

（2）希爾排序法。

希爾排序法是將整個(gè)無序序列分割成若干個(gè)小的子序列并分別進(jìn)行插入排序。

分割方法如下：

①將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列；

②在排序過程中，逐次減少這個(gè)增量，直到h減到1時(shí)，進(jìn)行一次插入排序，排序即可完成。

希爾排序的效率與所選取的增量序列有關(guān)。

3.選擇類排序法

選擇排序是通過每次從待排序序列中選出的最小值是元素，順序放在已排好序的有序子表的后面，直到全部序列滿足排序要求為止。下面就介紹選擇類排序法中的簡單選擇排序法和堆排序法。

（1）簡單選擇排序法。

進(jìn)行簡單選擇排序，首先從所有n個(gè)待排序的數(shù)據(jù)元素中選擇最小的元素，將該元素與第一個(gè)元素交換，再從剩下的n-1個(gè)元素中選出最小的元素與第二個(gè)元素交換。重復(fù)這樣的操作直到所有的元素有序?yàn)橹埂?/p>

簡單選擇排序需要比較n（n-1）／2次。

（2）堆排序法。

堆排序的方法如下：

①將一個(gè)無序序列建成堆；

②將堆頂元素與堆中最后一個(gè)元素交換。忽略已經(jīng)交換到最后的那個(gè)元素，考慮前n-1個(gè)元素構(gòu)成的子序列，只有左、右子樹是堆，可以將該子樹調(diào)整為堆。這樣反復(fù)下去做第二步，直到剩下的子序列空為止。

堆排序需要比較的次數(shù)為O（nlog2n）。

真題精選

對于長度為n的線性表，下列各排序法所對應(yīng)的比較次數(shù)中正確的是______。

A）冒泡排序?yàn)?span id="ken4pum" class="italic">n／2

B）冒泡排序?yàn)?span id="qij7mc9" class="italic">n

C）快速排序?yàn)?span id="zkdgvkt" class="italic">n

D）快速排序?yàn)?span id="vh7aecc" class="italic">n（n-1）／2

【答案】D

【解析】假設(shè)線性表的長度為n，則冒泡排序需要經(jīng)過n／2遍的從前往后掃描和n／2遍的從后往前掃描，需要比較次數(shù)為n（n-1）／2。快速排序法在最壞的情況下，比較次數(shù)也是n（n-1）／2。

常見問題

為什么只有二叉樹的前序遍歷和后序遍歷不能唯一確定一棵二叉樹？

在二叉樹遍歷中前序和后序中都可以肯定根節(jié)點(diǎn)，在中序是由左至根及右的順序，所以知道前序（或后序）和中序肯定能唯一確定二叉樹；在前序和后序中只能確定根節(jié)點(diǎn)而對于左右子樹的節(jié)點(diǎn)元素沒辦法正確選取，所以很難確定一個(gè)二叉樹。由此可見需要確定一棵二叉樹的基礎(chǔ)是必須得知道中序遍歷。