找到此分区问题的轴心

Question

好吧，假设我们有一个完成分区的数组，结果是

{3, 5, 3, 9, 17, 14, 24, 21, 19}

第一个分割步骤的支点是什么？

显然有不止一个答案，但我只找到了一个，是 9？还有我错过的吗？如果有人找到了其他答案，您能解释一下您是如何找到它的吗？

Answer 1

这个分区有两个可能的支点。

第一个是9排在第四位，很明显，前三个数都小于9，其余数都大于9。

还有一个是第一个位置的3，放在数组末尾的时候已经在partition之前的数组开头了，找不到更小的数比 3，因此不执行交换。

尝试以第一个3为基准进行分区，结果相同。假设左边的交换指针寻找一个大于或等于枢轴的数字，右边的交换点寻找一个小于枢轴的数字。

这意味着，对于数组 {3, 5, 3, 9, 17, 14, 24, 21, 19},

3 5 3 9 17 14 24 21 19
19 5 3 9 17 14 24 21 3 #Swap pivot to the end

[19] 5 3 9 17 14 24 21 3 
#Left locks 19 >= 3, right cannot find any number < 3, end of swapping

3 5 3 9 17 14 24 21 19
#Swap pivot back to the position where left and right pointers meet
#End of algorithm

找到此分区问题的轴心

Find the Pivot for this Partition Question

algorithm

sorting

quicksort

partition