: 推 LPH66: 所以一個常見的方法其實是先把 pivot 放在陣列"開頭" 04/09 07:17 : → LPH66: 接著用你的方法維護成 [pv][<pv ... <pv][>pv ... >pv] 04/09 07:18 : → LPH66: 最後再用你這一步想做的交換把 [pv] 擺在兩塊中間 04/09 07:18 : → LPH66: 概念上其實和你已經寫好的差不多, 只是不是另起變數存 pv 04/09 07:19 : → LPH66: 重點在於這一步既然要是陣列元素對換, 那就把 pv 也擺進去 04/09 07:20 : → LPH66: 定位問題就先找個好定位的地方放就好 (例如陣列開頭) 04/09 07:21 : 感謝回答，其實我原本寫的就是把pivot放最後的，這樣交換不會有問題沒錯，但就是想 : 試試看把pivot放中間，有沒有方法可以追蹤pivot最後換到的位子呢? : ※ 編輯: nasty1122 (101.9.7.42), 04/09/2019 15:09:44 相信你可能看過一種設計演算法的邏輯叫做「迴圈不變量 (loop invariant)」 它的概念是, 在一個迴圈裡我們會對一個資料結構進行更新 更新的過程可能會更動資料結構的組合 但是在迴圈的開始和結束時我們會要求資料結構具有某個性質 更新當中時破壞掉無所謂, 只要一圈動作作完時這個性質有回來就好 這個性質稱做這個迴圈的「迴圈不變量」 (叫「量」可能會以為只是某個數值, 但其實它是可以指任何我們想要的性質的) 這種設計的好處在於, 有一個明確的性質可以幫助迴圈內容的設計 而且這個性質也能夠在迴圈結束時證明這個迴圈確實做好了某些事 (本版一篇久遠之前的文章也有簡單談了 loop invariant: #13r5O_TK (C_and_CPP) ==== 上面引的這篇老文提到說通常, 這個不變量就是我們迴圈結束之後想要的結果 回到 quick sort 來看 這裡的迴圈不變量是 [pv][<pv ... <pv][>pv ... >pv] 這樣的內容排列 每一次迴圈就是加入下一個陣列元素, 然後把它排成符合這個不變量的排列 這樣就能知道為什麼迴圈中是寫成 if (下一元素 < pivot) 交換此元素和分界點元素; ==== 那麼現在你想要的是把這個不變量改成 [<pv ... <pv][pv][>pv ... >pv] 這樣的排列 這樣我們可以思考一下加入元素時要怎麼保持這個不變量 > pivot 時和前一種做法一樣什麼事都不用做 < pivot 時, 我們會需要把 >pv 區的第一個元素搬到後面, pv 後移, 再把新元素放進去 ┌┐┌─────┐ │↓│ ↓ [<pv ... <pv][pv][>pv ... >pv][new] ↑ │ └───────┘ 如果將 pv 所在索引值記錄在 pvidx 的話, 寫起來大概會像這樣: if (arr[i] < arr[pvidx]) { int temp = arr[i]; arr[i] = arr[pvidx+1]; arr[pvidx+1] = arr[pvidx]; arr[pvidx] = temp; ++pvidx; } ==== 可以看到, 同樣是分邊的想法, 不變量設定的方式不一樣寫出來的迴圈也就不一樣 因此也就有一種改進迴圈的方式是設法找到更好的不變量條件來用 繼續以 quick sort 為例, 同樣是分邊 原本保持 pv 在中間的做法有三次的移動元素 但 pv 一開始我們就拿著不用每次搬, 所以如果把不變量簡化成 pv 位置留空: [<pv ... <pv][ ][>pv ... >pv] 每一圈的移動就只剩下兩次 然後再考慮到 pv 原本也是陣列元素之一, 所以放回去比另外存更好 因此把不變量的兩半排在一起, pv 找個不會被碰到的位置放回陣列裡 就變成了這種不變量: [pv][<pv ... <pv][>pv ... >pv] 兩次的移動也合併成了一個交換了, 這就是你所看到過的常見 quick sort 實作 -- 有人喜歡邊玩遊戲邊上逼； 也有人喜歡邊聽歌邊打字。 但是，我有個請求， 選字的時候請專心好嗎？ -- 改編自「古 火田 任三郎」之開場白 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.192.32 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1554821189.A.75B.html