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

Question

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

ETC我从（位置 0,4 和 9）的中值中选择枢轴并选择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 中的字母是相同的，但我认为顺序很重要。谁能确定我哪里出错了，或者解决方案如何获得这种状态？任何事情都值得赞赏。

标签： algorithmsortingquicksorttheory

Answer 1

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

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