擁抱「資料結構」的「演算法」(21) - 快速排序法

 

前言

講完初等排序之後,接連三天會繼續介紹高等排序,今天就由快速排序法開始吧

生活常識

你有用過篩子嗎?像是篩選麵粉或是篩選盆栽的土壤,都會看到篩子的身影,篩子是一種過濾器,那面有很多小孔,體積大於過濾孔的物品會被留在篩子上面,而體積小於過濾孔的細碎物品則會通過篩子往下面掉,這時候我們下面通常會再多放一個接物品的盆子,這個過篩的動作,會把物品一分為二,分別是大於過濾孔的與小於過濾孔的,而過篩有一個重點就是要挑選合適的篩子,不然過濾孔過大等於物品,物品通通會通過篩子,等於是沒過濾,然而過濾孔太小,則物品都卡在篩子上面下不去,所以如何篩選出適合的物品其過濾孔很重要


圖片來源:https://www.pexels.com/zh-tw/photo/4099130/

專業知識 - Quick Sort

快速排序法採用分而治之法(Divide-and-conquer),把大問題切割成小問題,會於資料中找到一個基準值(Pivot),並將資料逐一與這個值相比較,最後可以得到兩個部分,分別為大於這個值小於這個值的數值,大於基準值的數值放在右邊,小於基準值的數值放左邊基準值就很像是我們使用的篩子,篩完之後物品就會被區分成兩塊

步驟 1 - 挑選基準值(Pivot)

常用的方式

  • 取亂數
  • 頭數、尾數、中間數排序後取中間值
    例如:1,5,7,9,8,6,3,第一個數為 1,最後一個數為 3 ,中間數為 9,由小至大排序後得到 1, 3, 9 可以取 3 做為基準值
  • 取數值的最左邊或做右邊

步驟 2 - 數值的比較

有一陣列稱為 array,數值共有 n 個,例如:6, 4, 9, 3, 5, 0, 7, 2, 8, 1,數值共有 10 個,需做兩件事情來與基準值做比較,才能將大於小於基準時的數值分類出來,假設基準值是 6

  • 由左往右
    使用變數 i ,紀錄搜尋的位置,i = 0, 2, 3, 4, 5, ..., n-1,讀取索引位置內的數值並與基準值比較,確認數值小於基準值,如果找到大於基準值的數值,將此索引位置記錄下來,例如:array[2] 的數值為 9 ,9 大於基準值 6,將 i = 2 記錄下來

  • 由右往左
    使用變數 j ,紀錄搜尋的位置,j = n-1, n-2, ..., 0,讀取索引位置內的數值並與基準值比較,確認數值大於基準值,如果找到小於基準值的數值,將此索引位置記錄下來,例如:array[9] 的數值為 1 ,1 小於基準值 6,將 i = 9 記錄下來

步驟 3 - 數值的交換

  • 當 i 值小於j 值,且 array[i] 大於 array[j] 則進行交換
    例如 i = 2 小於 j = 9,且 array[2] 的數值 9 大於 array[9] 的數值 1 ,則將兩個數字交換,將已知的兩數交換的方式,跟氣泡排序法一樣,就直接兩個數值的索引位置交換

  • 當 i 值大於等於j 值,也就是 i 與 j 位置交錯時,將 array[j] 與基準值交換
    例如 i = 7,j = 6 時,將 array[6] 的數值 2 與基準值的 6 交換位置,當基準值完成交換之後,就會發現,基準時的左邊都是小於基準值的數值:2, 4, 1, 3, 5,基準值的右邊都是大於基準值的數值:0, 6, 7, 8, 9,而且此時的基準值,就會在正確的位置上,之後都不會再被更動

詳細步驟可參考下圖



步驟 4 - 各別處理左區與右區

再針對左區或右區,在重新挑選基準值,例如左區有 2, 4, 1, 3, 5,可在此區重新挑基準值,例如以 2 為基準值,再重覆 1 ~ 3 步驟即可(遞迴),等到最後切到只剩單一元素時,即可完成所有數值的排序

分析

  • 最壞的情況
    https://chart.googleapis.com/chart?cht=tx&chl=O(n%5E2),每次挑基準值的時候,都剛好挑到最大值或最小值,例如:1, 2, 3, 4, 5, 6, 7, 8, 9,基準值挑到 1 ,則 1 要與 2, 3, 4, 5, 6, 7, 8, 9 一一比較,才知道 1 是最小值

  • 最好的情況
    O(n log n),挑選到好的基準值,可將資料切為一半,再根據其中一半再切一半,再分別去處理小的子區塊,切 log n 次,所以會花O(log n)時間,再加上每個數值要跟基準值相比較 n 次,花 O(n)時間,所以需花費 O(n log n)


今日小結

快速排序法看起來是不是很複雜,但就如同它的名字,快速排序法是號稱最快的排序法,不過當遇到最糟的情況就會慢很多哦!


今日謎題

演奏會過程舉辦了一個抽獎活動,答對以下謎題就可以獲得抽獎券一張,請將下列上下不對稱而且左右不對稱的字母刪掉:F、D、P、G、I、Q、J、V、I、D、R、Z、E,請將他刪除,你能成功或取得抽獎券嗎?

昨日解謎

謎題說明:使用謝耳排序法,由大至小排序 4, 2, 3, 5, 3, 2 ,這段數值總共有 6 個,區間值 = 3 ,第一步驟可將數值切成 2 個區塊 ( 6/3 = 2),各自在區塊內重新編號,並將相同編號的數值進行排序,即可得到 5 3 3 4 2 2 這個旋律 So Mi Mi Fa Re Re,歌曲就是小蜜蜂,因為小量的排序資料很容易用人眼就看出結果,所以解謎不使用結果,而是使用過程來來練習



留言

這個網誌中的熱門文章

CPE 一顆星選集題目說明與解答 - Java 筆記與心得分享

Visual Studio 自動排版格式化程式碼

1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明