第7章 排序

第7章 排序

任何通用的排序算法均需要NlogN次比較

7.1 預備知識

略

7.2 插入排序

插入排序思想：在已排序狀态插入新元素

插入排序的最壞情形和平均情形均為n的平方

7.3  一些簡單排序算法的下界

通過比較和交換來進行排序的算法本質上是消除序列中的逆序數，是以求解該算法的時間複雜度時，需要計算其排序序列的逆序數。

7.4 希爾排序

希爾排序需要一個最低為1的增量序列。

希爾排序的本質則是通過比較非相鄰元素來消除逆序數的進階插入排序版。

相對于隻比較相鄰元素的插入排序，希爾排序比較了非相鄰元素，保證消除了至少為1的逆序數，是以其性能有可能突破插入排序的n平方界。

希爾排序的增量序列最小為1，保證了序列每個都可被比較排序到，保證序列最終有序。

希爾排序過程中，通過不斷縮減增量序列，跳躍比較不同的元素。

一個k排序過的序列保持其k排序性。

k排序的一般思路：對于k，k+1，。。。n-1的每一個元素i，将其放到i，i-k，i-2k。。的合适位置上。

其實就是對k個子數組執行插入排序。

希爾建議的序列為開始序列為n/2的下限，後續序列為前面序列的一半，直至1。

使用希爾增量的最壞情形運作時間為n平方。

7.5 堆排序

堆排序利用了每次删除操作後空出的位置，将删除後的元素放到空出的位置節省記憶體。

7.6 歸并排序

歸并排序使用了所有流行排序中最少的比較次數。

歸并排序是分治算法思想的運用。

其本質是遞歸對兩個已排序子序列進行排序。

7.7 快速排序

快速排序一般采用三數中值分割法。

快速排序的本質是遞歸地将元素放在合适的位置。也正因為這樣，提供了篩選出第k大元素的nlogn算法。

快速元素一般對于遇到相等元素時采用停止的算法。

對于小數組，快速排序不如插入排序，是以當n小于20時，可進行插入排序。

快速排序一定考慮相等序列的情形，因為遞歸會将相等的元素放到一起。

7.8 排序算法的一般下界

略

7.9 選擇問題的決策樹下界

如果決策樹所有的葉子都有深度d或更深，則決策樹必須至少有2d個葉子。

對任何基于比較的算法，找最小元都必須至少使用N-1次比較。

從N個元素中找最小元的決策是必須至少有2的n-1次方個葉子。

7.10 對手下界

7.11 線性時間的排序：桶排序和基數排序

桶排序使用了額外的數組，利用空間換時間。通過使用數組的位置可以快速索引的特性，将需要排序的數組值與數值位置映射起來。

基數排序用于對數字範圍較大的數字的排序，通過依次對不同的位上的數排序，來達到對數的整體排序。

計數基數排序的友善之處在于解決基數排序時表的建立，通過引入一個額外數組用于記錄需排序值的位置，達到将值放到數組正确位置的做法。

7.12 外部排序

外部排序一般利用了歸并算法，通過将外存中的記錄讀到記憶體排序并寫回外存，接着依次讀取已經排序好的外存中的記錄進行邊讀取邊歸并操作。

多路合并改善了兩路合并的多次io的性能，可以通過使用優先隊列，對多路的記錄進行歸并排序。

多相合并則是在極大節約磁盤空間的情況下的合并算法。

替換選擇在與最優化的利用記憶體，盡量通過一次記憶體排序的記錄數的提高減少歸并的次數。

疑難點