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

来源：3-7 双路快速排序法

weibo_瘦不下来的胖胖儿_0

2017-10-18

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

return j;

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

写回答

1回答

liuyubobobo

2017-10-19

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

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

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

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 2

回答 2

回答 1

回答 7