資源描述：
《C語言快速排序算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、C語言快速排序算法(一)概述 快速排序(QuickSort)是一種有效的排序算法。雖然算法在最壞的情況下運行時間為O(n^2)，但由于平均運行時間為O(nlogn)，并且在內(nèi)存使用、程序?qū)崿F(xiàn)復雜性上表現(xiàn)優(yōu)秀，尤其是對快速排序算法進行隨機化的可能，使得快速排序在一般情況下是最實用的排序方法之一?！ 】焖倥判虮徽J為是當前最優(yōu)秀的內(nèi)部排序方法。(二)實現(xiàn) 快速排序的實現(xiàn)基于分治法，具體分為三個步驟。假設(shè)待排序的序列為L[m..n]?！ 》纸猓盒蛄蠰[m..n]被劃分成兩個可能為空的子序列L[m..pivot-1]和L[pivot+1.
2、.n]，使L[m..pivot-1]的每個元素均小于或等于L[pivot]，同時L[pivot+1..n]的每個元素均大于L[pivot]。其中L[pivot]稱為這一趟分割中的主元（也稱為樞軸、支點）?！ 〗鉀Q：通過遞歸調(diào)用快速排序，對子序列L[m..pivot-1]和L[pivot+1..r]排序。 合并：由于兩個子序列是就地排序的，所以對它們的合并不需要操作，整個序列L[m..n]已排好序。(三)性質(zhì) 內(nèi)部排序 快速排序是一種內(nèi)部排序方法。也就是說快速排序的排序?qū)ο笫亲x入內(nèi)存的數(shù)據(jù)?！ ”容^排序 快速排序確定元素位置的
3、方法基于元素之間關(guān)鍵字大小的比較?！ ∷谢诒容^方法的排序方法的時間下界不會低于O(nlgn)。這個結(jié)論的具體證明，請參考有關(guān)算法的書籍，例如《算法導論》（第一版）第8章（第二版在第七章QuickSort)?！ ≡诶硐肭闆r下，能嚴格地達到O(nlgn)的下界。一般情況下，快速排序與隨機化快速排序的平均情況性能都達到了O(nlgn)。 不穩(wěn)定性 快速排序是一種不穩(wěn)定的排序方法。簡單地說，元素a1,a2的關(guān)鍵字有a1.key=a2.key，則不穩(wěn)定的排序方法不能保證a1,a2在排序后維持原來的位置先后關(guān)系?！ ≡嘏判颉 ≡谂判虻?/p>
4、具體操作過程中，除去程序運行實現(xiàn)的空間消費（例如遞歸棧），快速排序算法只需消耗確定數(shù)量的空間（即S(1)，常數(shù)級空間）。 這個性質(zhì)的意義，在于在內(nèi)存空間受到限制的系統(tǒng)（例如MCU）中，快速排序也能夠很好地工作。(四)時空復雜度 快速排序每次將待排序數(shù)組分為兩個部分，在理想狀況下，每一次都將待排序數(shù)組劃分成等長兩個部分，則需要logn次劃分?！ 《谧顗那闆r下，即數(shù)組已經(jīng)有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序?qū)⒉恍彝嘶癁槊芭菖判颍钥焖倥判驎r間復雜度下界為O(nlogn)，最壞情況為O(n^2)。在實際應(yīng)用中
5、，快速排序的平均時間復雜度為O(nlogn)?！ 】焖倥判蛟趯π蛄械牟僮鬟^程中只需花費常數(shù)級的空間?？臻g復雜度S(1)。 但需要注意遞歸棧上需要花費最少logn最多n的空間。(五)隨機化算法 快速排序的最壞情況基于每次劃分對主元的選擇?；镜目焖倥判蜻x取第一個元素作為主元。這樣在數(shù)組已經(jīng)有序的情況下，每次劃分將得到最壞的結(jié)果。一種比較常見的優(yōu)化方法是隨機化算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴于輸入數(shù)據(jù)，而是由于隨機函數(shù)取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能
6、性僅為1/(2^n)。所以隨機化快速排序可以對于絕大多數(shù)輸入數(shù)據(jù)達到O(nlogn)的期望時間復雜度。一位前輩做出了一個精辟的總結(jié)：“隨機化快速排序可以滿足一個人一輩子的人品需求?！薄 ‰S機化快速排序的唯一缺點在于，一旦輸入數(shù)據(jù)中有很多的相同數(shù)據(jù)，隨機化的效果將直接減弱。對于極限情況，即對于n個相同的數(shù)排序，隨機化快速排序的時間復雜度將毫無疑問的降低到O(n^2)。(六)減少遞歸棧使用的優(yōu)化 快速排序的實現(xiàn)需要消耗遞歸棧的空間，而大多數(shù)情況下都會通過使用系統(tǒng)遞歸棧來完成遞歸求解。在元素數(shù)量較大時，對系統(tǒng)棧的頻繁存取會影響到排序的效
7、率。 一種常見的辦法是設(shè)置一個閾值，在每次遞歸求解中，如果元素總數(shù)不足這個閾值，則放棄快速排序，調(diào)用一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對系統(tǒng)遞歸棧的頻繁存取，節(jié)省了時間的消費?！ ∫话愕慕?jīng)驗表明，閾值取一個較小的值，排序算法采用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值T=10，排序算法用選擇排序?！ ￠撝挡灰螅駝t省下的存取系統(tǒng)棧的時間，將會被簡單排序算法較多的時間花費所抵消?！ ×硪粋€可以參考的方法，是自行建棧模擬遞歸過程。但實際經(jīng)驗表明，收效明顯不如設(shè)置閾值。(七)C例程 以下是C語
8、言權(quán)威《TheCProgrammingLanguage》中的例程，在這個例程中，對于數(shù)組v的left到right號元素以遞增順序排序?！ ?/Qsort.cbyTydus. #include intarr[]={
