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