二級C語言排序技術2

（1）交換類排序法交換類排序法是指借助數據元素之間的互相交換進行排序的壹種方法。冒泡排序法與快速排序法都屬於交換類排序方法。冒泡排序法是壹種最簡單的交換類排序方法，它是通過相鄰數據元素的交換逐步將線性表變成有序。假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後的掃描和n/2遍的從後往前的掃描，需要的比較次數為n(n–1)/2。但這個工作量不是必需的，壹般情況下要小於這個工作量。快速排序法也是壹種交換類的排序方法，但由於它比冒泡排序法的速度快，因此稱之為快速排序法。其關鍵是對線性表進行分割，以及對各分割出的子表再進行分割。（2）插入類排序法插入類排序法主要有簡單插入排序法和希爾排序法。簡單插入排序法，是指將無序序列中的各元素依次插入到已經有序的線性表中。在這種排序方法中，每壹次比較後最多移掉壹個逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n(n–1)/2次比較。希爾排序法對簡單插入排序做了較大的改進。它是將整個無序序列分割成若幹小的子序列分別進行插入排序。希爾排序的效率與所選取的增量序列有關。在最壞情況下，希爾排序所需要的比較次數為O(n1.5)。（3）選擇類排序選擇類排序主要有簡單選擇類排序法和堆排序法。簡單選擇排序法的基本思想是：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置）；然後對剩下的子表采用同樣的方法，直到子表空為止。對於長度為n的線性表，在最壞情況下需要比較n(n–1)/2次。堆排序法也屬於選擇類排序法。具有n個元素的序列（h1, h2, …, hn），當且僅當滿足條件： 或 (i=1, 2, …, n/2）時稱之為堆。可見，堆頂元素（即第壹個元素）必為最大項。堆排序的方法對於規模較小的線性表並不適合，但對於較大規模的線性表來說是很有效的。在最壞情況下，堆排序需要比較的次數為O(nlog2n)。