__partition2中最后 swap( arr[l] , arr[j] ) ,return j;为什么是返回j

Question

swap(arr[l],arr[j]);

return j;

我知道为什么交换arr[l],arr[j]，但是不太明白为什么是返回j 的值，因为交换只是交换他们的数值啊，i，j 没有交换位置啊

Answer 1

liuyubobobo 2017-10-19 01:23:45

我们最后要返回的是partition以后最后那个标定点的位置。l和j的元素交换位置以后，我们在partition过程中一直使用的那个标定点（pivot）就从l的位置变到了j的位置上，所以返回j。

如果返回l，岂不就永远返回每一段数组的第一个元素的位置了？：）

运行一个小样本数据量，比如只有8个元素进行排序，试着跟跟看？搞清楚算法的执行顺序和每一步执行后数据具体是怎么改变的，返回的到底是谁，和自己想的是不是有出入，如果有出入自己想的哪里不对，是一个非常非常好的理解算法的方式哦：）加油！