擁抱「資料結構」的「演算法」(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 步驟即可(遞迴)，等到最後切到只剩單一元素時，即可完成所有數值的排序
分析
最壞的情況
，每次挑基準值的時候，都剛好挑到最大值或最小值，例如：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，歌曲就是小蜜蜂，因為小量的排序資料很容易用人眼就看出結果，所以解謎不使用結果，而是使用過程來來練習
留言
張貼留言