对列表M,E,R,G,E,S,O,R,T应用快速排序

Question

Answer 1

在字母下面使用^表示它是一个枢轴，使用*表示它已经枢轴。如果一个分区的长度为奇数，我选择“Rounded down Middle”（分区长度4将有第二个项目作为枢轴）。

请注意，在第4行中，有两个r，其中一个是枢轴。在这种情况下，副本（另一个R)可以在任何一边。

编辑：比较两个字母时，需要根据它们在字母表中的位置对它们进行排序。如果您基于它们的相对位置“排序”，您将永远不会移动任何元素，因此您自然不会对列表进行排序。

编辑#2:我使用的算法是，毫不奇怪，快速排序。

MERGESORT -> EEMRGSORT
    ^         ^

EEMRGSORT -> EEMRGORST
^*   ^       ^*     ^

EEMRGORST -> EEGMRORST
**  ^  *^    **^    **

EEGMRORST -> EEGMORRST
*** ^  **    ***  ^ **

EEGMORRST -> EEGMORRST
***^ *^**    ***^ *^**

EEGMORRST -> EEGMORRST
****^****    ****^****

EEGMORRST -> Complete
*********

如果我犯了错误，请纠正我。