接著上一篇說快排

婁煩ssl適用于網(wǎng)站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應用場景，ssl證書未來市場廣闊！成為成都創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18982081108（備注：SSL證書合作）期待與您的合作！

改進一下上一篇所寫的快排。

這里的快排方法是霍爾方法。不過這個方法還沒完全?？梢园l(fā)現(xiàn)，排一遍后，就會分成兩個區(qū)間繼續(xù)快排，然后左右兩個區(qū)間又會各自分出兩個區(qū)間繼續(xù)排，所以這其實是一個滿二叉樹結(jié)構(gòu)，因為不一定每個區(qū)間都需要排。

現(xiàn)在這個算法的時間復雜度是多少？如果單趟排序，那么應該是一個O(N)。具體應該走多少次？

這個二叉樹結(jié)構(gòu)的高度是logN，數(shù)據(jù)總數(shù)為N。第一次排序后，到了第二層，左右兩個區(qū)間繼續(xù)排，這時候要排的數(shù)據(jù)總數(shù)就變成N - 1.第三層就變成了N -? 3.，然后一直排下去。不過持續(xù)減下去N也不會減到0，假設N是1000，那么總體的高度大約就是10，所以最終N也沒減少太多。

所以整體時間復雜度應該N * logN。不過快排的時間復雜度也并非是這個，畢竟不可能每次都在排序。對于快排來說，無論是順序還是逆序，似乎每一次都要排序，這時候的時間復雜度可以看出來是N方，所以有序?qū)τ诳炫艁碇v就是很不好的情況，相反，無序才是快排最適合的。不過實際中我們無法決定數(shù)據(jù)是什么序。假如是逆序或者順序，選擇前后兩端作為key，都需要所有數(shù)據(jù)全部走一遍才行。為了解決這個問題，在快排之前，先把大最小以及中間那個數(shù)字拿出來做比較，選中杯，這樣即使是一個有序的數(shù)據(jù)集，也不會每次都要全部比較排序一遍；這個方法放到無序數(shù)據(jù)里也沒關(guān)系，這對無序并沒有多少影響，當然也有可能在無序數(shù)據(jù)里就正好選出了最小的那個數(shù)，但概率確實小，不必考慮。

我們看一下有序和無序數(shù)據(jù)快排的效率，先改成有序10萬個數(shù)字。

再改成無序

這當然是在release模式下運行的，如果是在debug下運行，有序數(shù)據(jù)其實就崩了，因為現(xiàn)在這個快排是個遞歸寫法，對于有序數(shù)組，代碼需要一直往下開棧，開到最后才停，所以棧爆了。而且，僅從數(shù)字上看也能看出，快排面對有序或者接近有序是低效的。

現(xiàn)在我們寫一下三數(shù)取中算法。不過確定中間值后key還是=begin，只是在這之前把中間值和begin的值互換一下。

加入三數(shù)取中后，再看有序快排

這就正常了。再看無序

當然選key問題還有別的解決辦法，比如選出隨機數(shù)做key。

選key結(jié)束后，現(xiàn)在這個快排還有另一個問題?？炫艜饾u減少排序的數(shù)據(jù)量，如果N是10，排序兩個層后每個區(qū)間也就剩兩三個數(shù)據(jù)了，回想一下剛才說的二叉樹結(jié)構(gòu)，如果繼續(xù)使用快排，那么又得選key， 繼續(xù)調(diào)用棧幀，這樣的話不高效啊，費空間，而且實際上10個數(shù)也是一個很小的數(shù)據(jù)了，然而10個數(shù)我們還需要做好幾次遞歸，小題大做了。所以小數(shù)據(jù)時就不用快排了，當然其他用遞歸的排序也不選了，冒泡和選擇排序也先去掉，所以就剩直接插入，希爾，堆排序了。

實際上會選擇直接插入排序。希爾排序會先預排，讓大的數(shù)盡快走到后面，然后再插入排序，不過小數(shù)據(jù)上希爾排序也不一定有優(yōu)勢。

我們看一下10000個數(shù)排序

所以總共就差距幾毫秒而已。沒必要再去做預排序了。而堆排序其實還要向下調(diào)整，建堆，所以不如簡單的一個思路，直接插入即可。

10個數(shù)的遞歸，是經(jīng)歷三層排序才會結(jié)束。如果這樣的小數(shù)據(jù)用插入排序，實際上會省出很多的時間。按照二叉樹結(jié)構(gòu)，第一層遞歸1次，第二層2次，第三層4次，第4層8次，而最后一層就是2的h次方? -? ?1.即使去掉最后一層，也會減少一半的遞歸次數(shù)，而去掉最后三層就去掉了80%多的次數(shù)?？梢詭刖唧w的數(shù)來計算，會發(fā)現(xiàn)最后一層占了一半，而倒數(shù)第二層大約占總次數(shù)的25%。所以小區(qū)間的優(yōu)化很有必要。

現(xiàn)在寫一下代碼

做一下測試，這里效果不如三數(shù)取中那么明顯，所以我們?nèi)『艽蟮臄?shù)，就不看插入排序了。

百萬個數(shù)據(jù)?

千萬個

千萬個有序

不過這里用的測試很單一，代碼很簡單，只是看一個大概的效果改變。以及release模式對于遞歸的優(yōu)化也很大。

debug下百萬無序

有序的話會更快

不過千萬個數(shù)據(jù)debug下就難受了。

挖坑法

快排其實不止這一個方法，這個方法是霍爾方法，而快排還有另外兩個辦法，挖坑和雙指針。

先把代碼區(qū)分出來，三個方法都取名叫partsort

挖坑法依然要用到key，不過key的用法不一樣，key會先存一個值，這個值對應的位置就形成一個坑位，然后左右LR開始走，R找到比key小的，然后和那個坑位互換一下，R形成新的坑位，然后L找比key大的值，和坑位互換一下，L處形成新的坑位。這個方法走完一次后的數(shù)據(jù)順序和霍爾方法后的順序不一樣。

這里還是要找中杯。這個方法和霍爾有些像，實現(xiàn)起來也不算難

雙指針法

雙指針prev，cur，這個方法理解后代碼就會很容易寫出來。假設選擇0下標為key，prev指向0，而cur指向1下標處。cur往后走，如果小于key，那么prev往后走一步，并互換一下；遇到大于key的值后，prev停下，cur繼續(xù)往后走，等再次找到小的，那么按照上句所寫，prev往后走一步，來到一個大的值，互換一下。當然這里持續(xù)地往后走，我們一定要考慮越界問題，以及如果cur和prev處于同一位置，那么此時的互換可以避開一下，節(jié)省不必要的操作。

兩個swap之前和之后的代碼暫且不管，重點在中間。cur一開始就在prev的后一步；++prev ！= cur就是避免同位置互換的操作。

非遞歸快排

以上都是遞歸排法，但畢竟需要一直開棧，所以非遞歸寫法是很必要的。

這個可以和斐波那契數(shù)列的做法相似，數(shù)列是把第一個第二個直接寫了出來，然后循環(huán)，快排的非遞歸也是改循環(huán)，不過需要借助棧。

先想一下遞歸。先遞歸左，然后回去再遞歸右，區(qū)間的變化是可以捕捉到的，用棧也一樣，棧保存區(qū)間，我們就可以和遞歸一樣訪問不同的區(qū)間了。

假設一個10個數(shù)的數(shù)組，棧里進去0和9下標后，先放進6和9，再放0和4，這樣就能先改變[0, 4]區(qū)間的順序了。

先進入最一開始的左右兩端下標。right拿到一個，left拿到一個，選好key，就開始分區(qū)間排序。如果說走到最后，區(qū)間已經(jīng)不存在了或者只存在一個值，那就不需要再push了，所以呀有兩個if作為判斷。只要棧中還有數(shù)據(jù)，我們就需要繼續(xù)循環(huán)，所以while判斷條件是不為空。整個過程也就結(jié)束了。

下一篇繼續(xù)寫排序

結(jié)束。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標題：初階數(shù)據(jù)結(jié)構(gòu)學習記錄——??排序（2）-創(chuàng)新互聯(lián)
分享地址：http://aaarwkj.com/article14/dohpge.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供建站公司、關(guān)鍵詞優(yōu)化、定制網(wǎng)站、網(wǎng)站排名、企業(yè)網(wǎng)站制作、移動網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)