: 推 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/cn.aspx?n=bbs/C_and_CPP/M.1554821189.A.75B.html