快速排序:为什么要将轴心移到末尾？

Question

首先将所选的pivot元素移动到数组末尾的动机是什么？我能看到的唯一一件事是，当递增较低的索引i时，我们不需要检查i

是这样吗？

塔克恩斯

安迪

Answer 1

枢轴被移动到数组的末尾，因为在移动其他元素之前，它不知道它将在哪里结束。为了避免在每次比较后不断地移动整个数组的元素，将轴心放在末尾，直到数组的其余部分排序完毕(对于快速排序的那一步)，然后将其放在正确的位置。这意味着数组只需要移位两次(一次在开始，一次在结束)，而不是在每次比较之后。