: 推 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 实作