要把 pivot 放中间也是可以唷, 不过这要引入视图(view) 的概念.
简单说就是提供一个抽象化层, 让我们看到的阵列不是实际上的阵
列, 而这个抽象化的目的是让我们看不到 pivot, 如此就可以解决
partition 时会把 pivot 搬来搬去的问题
┌──┬──┬──┬──┐
视图 │ 3 │ 4 │ 2 │ 5 │
└──┴──┴──┴──┘
┌──┬──┬──┬──┬──┐
阵列 │ 3 │ 4 │ 1 │ 2 │ 5 │
└──┴──┴──┴──┴──┘
(pivot)
在提供这层抽象化前, 首先得面对的问题就是索引转换. 由上图可
以看到元素 5 在视图里的索引是 3, 但在阵列里的索引却是 4,
不过这个转换并不会太复杂
另外在 partition 的最后, 要稍微注意 pivot 摆放的位置, 其他
就没什么特别的地方. 实作可以参考下面的范例
无抽象化: https://bit.ly/2X13mEN
有抽象化: https://bit.ly/2IaFVWt