1回答

liuyubobobo

2017-08-31

将arr[l]和arr[j]两个元素交换位置：）

至于为什么要交换这个位置，和我们之前介绍的partition最后交换位置的原因一样。看一下我们课程里的示意图：

设想一下，当索引i和索引j交汇以后，我们还需要将v元素放在合适的位置，才能最终完成partition，此时，只需要将v元素（索引为l）和索引j所在的元素交换位置就好了。为什么是索引j？因为在这个循环结束的时候，索引j将指向橙色部分的最后一个元素（相应的，索引i指向紫色部分第一个元素），和索引j的位置交换元素以后，v左边的就都是橙色部分；v右边的就都是紫色部分。

可以尝试自己画图看，或者实际使用一个小的测试用例在程序里跟一下，或许能更直观地理解。最好对比一下我们在3-6的排序算法中的这步交换。同时，我们在后续的三路快排，依然需要这步交换：）

加油！

3

4

weibo_瘦不下来的胖胖儿_0

在最后交换时，只是交换了arr[i],arr[j]的位置啊，并没有交换i,j啊，还是没有明白为什么是j

2017-10-18

共4条回复