我从解决方案中得到不同的快速排序结果

Question

问题是对 ELECTRONIC 一词进行快速排序。我正在手动处理每一行，并且给出的解决方案是逐步的。第一步之后，我的状态与解决方案不同，不明白为什么。

我从 ETC（位置 0,4 和 9）和 select E 的中位数中选择枢轴。这个枢轴与最后一个位置 9 交换，并给出：

0123456789
CLECTRONIE

我从左边的 C 增加 i 并从右边的 I 减少 j 并最终交换位置 1(L) 和 4(C)给予

0123456789
CCELTRONIE

继续分别递增和递减 i 和 j，最终与位置 3 的 i 交叉，L，并与位置 9 的枢轴交换，得到：

0123456789
CCEETRONIL

现在在位置 3 的枢轴上，我认为分区是

CCE |E| TRONIL

但我的解决方案是：

Quicksort ELECTRONIC
choose pivot: median(E,T,C)=E
partition using E: ECC|E|LTRONI
...

我知道 Sl 和 Sr 中的字母是一样的，但我认为顺序很重要。谁能确定我哪里出了问题，或者解决方案如何获得这种状态？不胜感激。

Answer 1

您的分区实现了主要目标 - 左侧部分包含较少（或相等）的元素，右侧部分包含较大的元素。分区完成。任务 （当前阶段）已成功完成。

这些部分的元素顺序取决于分区实现（有不同的方案），不影响排序的正确性和速度。