A 講解:
快速排序法 平均時間複雜度 O(n lg n) 但最糟測資會到 O(n^2) 非為一個stable sort
但總體來說 被公認為最有效率排序演算法
其實C語言函式庫內就有提供 但這裡要做一個實做來了解內部運作
基本概念就是 先選一個"鍵值" (程式碼變數splitting)
比鍵值小者丟到左邊 大者右邊
接著左右邊各用遞迴不斷的繼續分堆 分成更小的堆
直至只剩下一個元素(故遞迴終止條件設為 left < right)
用圖形來解釋如下:
(25) 18 17 66 31 10 28 9 1 --------------- 第一次選做splitting " () "
[10] 18 17 1 9 (25) [28] 31 66 --------------- 第二次選做splitting " [] "
{1} 9 [10] {17} 18 (25) [28] {31} 66 --------------- 第三次選做splitting " {} "
你會發現當遞迴停止時(各堆剩下一個) 資料也由小到大排好了
至於如何實做的細節 可以先參考程式碼
有一個 do - while 的迴圈 可說是Qsort的精隨
至於這個迴圈在做什麼事呢? 一樣用圖形講解:
其中i = right, j = left + 1
對i來說 只要"遇到比鍵值還小的數"就停止
對j來說 只要"遇到比鍵值還大的數"就停止
然後當兩邊都停止時 就可以交換囉!! 所以 66 和 1 交換 31 和 9 交換
這時 你會發現陣列內存資料會變成這樣:
(25) 18 17 1 9 10 28 31 66
接著我們要把 25 移到中間
所以我們把他和 10 做交換 所以陣列內存資料會變成這樣:
10 18 17 1 9 (25) 28 31 66
如此一來 就分成大小兩堆了
接著左右兩邊做一樣事情就OK了
可以試著想想
這筆測資跟 {9, 8, 7, 6, 5, 4, 3, 2, 1}
你一筆比較耗時間呢
可以用追蹤的方式去看看喔
B 範例例題如下:
先輸入資料數 即陣列大小
接著輸入一筆未排序測資
請輸出排序後的資料 並在每筆測資後空一行
EX:
Input:
9
25 18 17 66 31 10 28 9 1
Output:
1 9 10 17 18 25 28 31 66
C 程式碼如下:
留言列表
