說明：該系列博客整理自《算法導論(原書第二版)》，但更偏重于實用，所以晦澀偏理論的內(nèi)容未整理，請見諒。另外本人能力有限，如有問題，懇請指正！

? ? 在第一部分--第2章中，介紹了兩種對n個實數(shù)進行排序的算法。插入排序?的最壞情況運行時間為Θ?( n2)，但其算法的內(nèi)循環(huán)是緊密的，對小規(guī)模輸入來說是一個快速的原地排序算法(在排序輸入數(shù)組時，只有常數(shù)個元素被存放到數(shù)組以外的空間中去)。合并排序?有著較好的漸近運行時間Θ(?nlgn)，但其中的MERGE程序不在原地操作。

? ? 在本部分中我們要介紹另外兩種對任意實數(shù)進行排序的方法：第6章的堆排序、第7章的快速排序。

? ? 第6章介紹堆排序，它可以在Θ(?nlgn)時間內(nèi)對n個數(shù)進行原地排序。這種算法用到一種重要的稱為堆的數(shù)據(jù)結(jié)構(gòu)，還要用它實現(xiàn)優(yōu)先級隊列。

? ? 第7章介紹快速排序，他是另一種對n個數(shù)進行原地排序的算法，但是它的最壞情況運行時間為Θ(?n2)。它的平均運行時間是Θ(?nlgn)，在實際中常常優(yōu)于堆排序算法。就像插入排序算法一樣，快速排序的代碼也比較緊湊，所以它的運行時間中隱含的常數(shù)因子就很小。對于大輸入數(shù)組的排序來說，這是一個很常用的算法。

? ? 通過第8章的決策樹模型，證明了任何對n個輸入進行排序的比較排序算法，其最壞情況運行時間的下界為Ω?( nlgn)，說明合并排序和堆排序都是漸近最優(yōu)的比較排序算法。

? ? 第8章，介紹非比較類排序算法，其運行時間可以突破Ω?( nlgn)的下界，不過計數(shù)排序、基數(shù)排序、桶排序都有使用的前提條件。例如，計數(shù)排序算法假定輸入數(shù)取自集合{0,1,2,...,k}。通過利用數(shù)組下標來確定元素的相對次序，該算法可以在Θ( k+n)時間內(nèi)完成對n個數(shù)的排序，這樣當k=O(n)時，計數(shù)排序的運行時間就與輸入數(shù)組的規(guī)模呈線性關(guān)系。基數(shù)排序算法可以用來擴大計數(shù)排序的使用范圍。如果有n個整數(shù)要排序，每個整數(shù)都有d位，且每位都可以取到k個可能值，則基數(shù)排序就可以在Θ(d* (k+n))時間內(nèi)完成排序。當d是個常數(shù)，k=O(n)時，基數(shù)排序就以線性時間運行。桶排序要求了解各個數(shù)在輸入數(shù)組中的概率分布，如果是絕對的均勻分布，則桶排序的效果最好。它可以對均勻分布在半開區(qū)間[0,1)上的n個實數(shù)以平均情況時間O(n)進行排序。

? ? 第9章，中位數(shù)和順序統(tǒng)計學。在一個由n個數(shù)構(gòu)成的集合上，第i個順序統(tǒng)計是集合中第i小的數(shù)。如果未學過本章，我們可能先排序，再查找，采用比較類排序的話，其時間復雜度為Θ(?nlgn)，采用非比較排序的話，其時間復雜度為Θ(n)。在本章中讀者將會看到，即使輸入數(shù)組中的各元素為任意實數(shù)，我們?nèi)阅茉?i>Θ(n)時間內(nèi)找到第i小元素。我們將給出一個算法，偽代碼很緊湊，最壞情況運行時間為Θ(?n2)，但平均情況下為線性時間。另外，還將給出一個更復雜的算法，其最壞情況運行時間為Θ(?n)。

? ? 本部分需要的數(shù)學背景知識說明：對快速排序、桶排序和順序統(tǒng)計量算法進行平均情況分析時，用到了概率論方面的知識(相關(guān)內(nèi)容可參見附錄C和第5章中的概率分析和隨機算法的材料)。順序統(tǒng)計學的最壞情況線性時間算法的分析，包含了比本部分其他最壞情況分析更復雜的數(shù)學內(nèi)容。

排序分類

1、比較排序

? ? 1）、插入排序：原地對任意實數(shù)進行排序

? ? 2）、合并排序：非原地對任意實數(shù)進行排序

? ? 3）、堆排序：非原地對任意實數(shù)進行排序。以堆排序為基礎(chǔ)，還了解了優(yōu)先級隊列。

? ? 4）、快速排序：原地對任意實數(shù)進行排序

2、非比較排序

? ? 1）、計數(shù)排序

? ? 2）、基數(shù)排序

? ? 3）、桶排序

3、中位數(shù)和順序統(tǒng)計

? ? 1）、中位數(shù)和順序統(tǒng)計

? ? 2）、動態(tài)順序統(tǒng)計