老师： __partition2中最后 swap( arr[l] , arr[j] ) 这句是什么意思啊？

Question

老师： __partition2中最后 swap( arr[l] , arr[j] ) 这句是什么意思啊？ 

Answer 1

liuyubobobo 2017-08-31 00:29:25

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

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

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

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

加油！

• 提问者 慕粉2233184011 #1

  为什么要交换位置?

• liuyubobobo 回复 提问者 慕粉2233184011 #2

  我修改在了以上回答中。

• klosero #3

  一样的疑问，看见回答就懂了，我误认为i会指向橙色的最后一个，赞

点开查看后面1条评论