快速排序里的學問:樞紐元選擇與算法效率

樞紐元選擇也有學問
服務器君一共花費了167.878 ms進行了5次數據庫查詢,努力地為您提供了這個頁面。
試試閱讀模式?希望聽取您的建議

選擇首尾元素做樞紐元

通常的、沒有經過充分考慮的選擇是將第一個或最后一個元素用作樞紐元。選擇第一個元素作為樞紐元的程序例子可以參考專題的前一篇《快速排序里的學問:霍爾快排的實現》,而選擇最后一個元素用作樞紐元的程序例子則可以參考《快速排序里的學問:快速排序的過程》這個算法導論里的例子。

選擇最后一個元素作為樞紐元的排序過程是這樣的:

如果輸入是隨機的,那么這是可以接受的,但是如果輸入是預排序的或者是反序的,那么這樣的樞紐元就產生一個劣質的分割,因為所有的元素不是被劃入S1就是被劃入S2。更有甚者,這種情況發生在所有的遞歸調用中。

實際上,如果第一個元素用作樞紐元而且輸入是預先排序的,那么快速排序所花費的時間將是二次的。然而,預排序的輸入(或者有一大段預排序數據的輸入)也是相當常見的,因此,使用第一個元素作為樞紐元的算法效率不是很高的。

另一種想法是選取前兩個互異的鍵中的較大者作為樞紐元,但這和只選取第一個元素作為樞紐元效率也差不多。

隨機選取樞紐元

一種安全的方針是隨機選取樞紐元。

一般來說這種策略非常安全,除非隨機數生成器有問題,因為隨機的樞紐元不可能總在接連不斷地產生劣質的分割。另一方面,隨機數的生成一般是昂貴的,根本減少不了算法其余部分的平均運行時間。

三數中分割法

一組N個數的中值是第[N/2]個最大的數。樞紐元的最好的選擇是數組的中值。

可是,這很難算出來,并且會明顯減慢快速排序的速度。這樣的中值的估計可以通過隨機選取三個元素并用它們的中值作為樞紐元而得到。事實上,隨機性并沒有多大的幫助,因此一般的做法是使用左端、右端和中心位置上的三個元素的中值作為樞紐元。顯然使用三數中值分割法消除了預排序輸入的不好情形。

這種樞紐元選擇的的快排,效率可是相當高的。

快速排序還很有很多各種變種,我們這里只研究幾個有代表性的算法。

延伸閱讀

此文章所在專題列表如下:

  1. 快速排序里的學問:從猜數字開始
  2. 快速排序里的學問:再看看稱球問題
  3. 快速排序里的學問:信息熵
  4. 快速排序里的學問:快速排序的過程
  5. 快速排序里的學問:霍爾與快速排序
  6. 快速排序里的學問:霍爾快排的實現
  7. 快速排序里的學問:樞紐元選擇與算法效率
  8. 快速排序里的學問:隨機化快排

本文地址:http://www.snpmgr.live/librarys/veda/detail/2397,歡迎訪問原出處。

不打個分嗎?

轉載隨意,但請帶上本文地址:

http://www.snpmgr.live/librarys/veda/detail/2397

如果你認為這篇文章值得更多人閱讀,歡迎使用下面的分享功能。
小提示:您可以按快捷鍵 Ctrl + D,或點此 加入收藏

閱讀一百本計算機著作吧,少年

很多人覺得自己技術進步很慢,學習效率低,我覺得一個重要原因是看的書少了。多少是多呢?起碼得看3、4、5、6米吧。給個具體的數量,那就100本書吧。很多人知識結構不好而且不系統,因為在特定領域有一個足夠量的知識量+足夠良好的知識結構,系統化以后就足以應對大量未曾遇到過的問題。

奉勸自學者:構建特定領域的知識結構體系的路徑中再也沒有比學習該專業的專業課程更好的了。如果我的知識結構體系足以囊括面試官的大部分甚至吞并他的知識結構體系的話,讀到他言語中的一個詞我們就已經知道他要表達什么,我們可以讓他坐“上位”畢竟他是面試官,但是在知識結構體系以及心理上我們就居高臨下。

所以,閱讀一百本計算機著作吧,少年!

《C程序設計語言(第2版新版)》 克尼漢 (作者), 等 (作者, 譯者), 徐寶文 (譯者)

《C程序設計語言》(第2版新版)是由C語言的設計者Brian W.Kernighan和Dennis M.Ritchie編寫的一部介紹標準C語言及其程序設計方法的權威性經典著作。全面、系統地講述了C語言的各個特性及程序設計的基本方法,包括基本概念,類型和表達式、控制流、函數與程序結構、指針與數組、結構、輸入與輸出、UNIX系統接口、標準庫等內容。

更多計算機寶庫...

燃烧吧足球登陆