快速排序學習總結

昨天花了一天的時間學習總結冒泡排序，今天下決心把數據結構的相關內容，各種排序，樹，
查找算法等都大概學習了一遍，把時間復雜度和空間復雜度等概念理清了，終于有了一點點
的踏實感，因為自己沒考研，本科基礎也沒打牢，總感覺自己跟任何一個人都有一大段的差距，
連寫程序和找實習工作都覺得自己很沒信心，缺少底氣，因為一些研究生里面大家都會的基礎
知識我絲毫不懂，真是太打擊自己了！！

自己的近期安排：

今天總結了快速排序，hash函數等知識之后，明天開始就要踏踏實實的看軟件測試的論文了！！
在看論文的同時，如果想練練手，最好堅持把上學期的“決策樹”的作業(yè)實現了，這樣自己
就有信心面對一切了！！

另外，好好上李老師數據挖掘的課！千萬不要遲到，最好6點10分就要去到新信息樓！好好學習，
去圖書館借幾本好書，提前學習和準備！

還有，明天別忘了問問解婷婷和楊惠她們的英文論文都是從哪下的？怎么搜索，比如，Proges的使用？
怎么知道哪些英文論文比較好？

好了，現在言規(guī)正傳，學習快速排序：

快速排序和冒泡排序都是交換排序類型，快排的算法思想是：
每次選一個基準值（比如第一個數），讓小于這個基準值的數向左移，大于這個基準值的數向右移，
一趟移動之后，這個基準值就定位到合適的位置了，它的左邊的數比它小，右邊的數比它大；一趟可以
定位一個數，左邊和右邊分別遞歸，n-1趟后所有數就都定位到合適位置了！

算法分析
??? 　快速排序的時間主要耗費在劃分操作上，對長度為k的區(qū)間進行劃分，共需k-1次關鍵字的比較。

（1）最壞時間復雜度
??? 　最壞情況是每次劃分選取的基準都是當前無序區(qū)中關鍵字最小(或最大)的記錄，劃分的結果是基準左邊的子區(qū)間為空(或右邊的子區(qū)間為空)，而劃分所得的另一個非空的子區(qū)間中記錄數目，僅僅比劃分前的無序區(qū)中記錄個數減少一個。
??? 　因此，快速排序必須做n-1次劃分，第i次劃分開始時區(qū)間長度為n-i+1，所需的比較次數為n-i(1≤i≤n-1)，故總的比較次數達到最大值：
?????????????? Cmax = n(n-1)/2=O(n2)
??? 　如果按上面給出的劃分算法，每次取當前無序區(qū)的第1個記錄為基準，那么當文件的記錄已按遞增序(或遞減序)排列時，每次劃分所取的基準就是當前無序區(qū)中關鍵字最小(或最大)的記錄，則快速排序所需的比較次數反而最多。

（2） 最好時間復雜度
??? 　在最好情況下，每次劃分所取的基準都是當前無序區(qū)的"中值"記錄，劃分的結果是基準的左、右兩個無序子區(qū)間的長度大致相等。總的關鍵字比較次數：
??????? 0(nlgn)
注意：
??? 　用遞歸樹來分析最好情況下的比較次數更簡單。因為每次劃分后左、右子區(qū)間長度大致相等，故遞歸樹的高度為O(lgn)，而遞歸樹每一層上各結點所對應的劃分過程中所需要的關鍵字比較次數總和不超過n，故整個排序過程所需要的關鍵字比較總次數C(n)=O(nlgn)。
??? 　因為快速排序的記錄移動次數不大于比較的次數，所以快速排序的最壞時間復雜度應為0(n2)，最好時間復雜度為O(nlgn)。

具體的算法描述、代碼實現、算法分析和動畫演示參見：
數據結構自考網
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.4.htm


附排序的面試題：
來自：http://www.javaref.cn/topics/Question/10566.html
問題：?

a)冒泡 (bubble sort) 和快速排序 (quick sort) 的區(qū)別？它們的時間復雜度？

冒泡：每趟排序將最大值安置到最后一個位置上，時間復雜度為 O(n 平方 ).
快速排序法是對起泡排序法的一種改進，
基本思想是通過一趟排序將待排序紀錄分割成獨立的兩部分，其中一部分紀錄的關鍵字
均比另一部分紀錄的關鍵字小，則可以分別對這兩部分紀錄繼續(xù)進行排序，以達到整個序列有序。
時間復雜度為 O(NlogN).?

疑問：快排的最壞時間復雜度是O(n 平方 )，最好時間復雜度到底是 O(Nlog2N)，還是 O(NlgN)？？
按照“數據結構自考網”的分析應該是O(Nlog2N)，但是《數據結構》書上277上的分析，似乎O(Nlog2N)
和O(NlgN)都是合理的，到底是什么呢？明天問問解婷婷吧。

b)在什么情況下快速排序的效果最差？ 答案：輸入數據逆序排列時效果最差，蛻化成冒泡????