寻找Kth最小元素

Question

有人能解释我做错了什么吗？我想找k个最小的元素，但有些地方出错了)

示例:我有未排序的数组int[] uA = {2、9、4、13、11、7、8}；我以"9“作为枢轴元素，在第一次分区(快速排序)迭代之后，我将得到这个数组{2、8、4、7、11、13、9}。中间指针将显示在"11“处。这到底意味着什么？并不是所有的元素都比11大11。11根本不是在“正确的地方”。但是，例如，我想返回第五个最小元素(11)。

Answer 1

枢轴不是在正确的位置，您应该将枢轴放在分区末尾的正确位置，以找出枢轴的位置。(您真的不需要关心中间元素)，那么您可以使用这些信息来计算Kth最小元素。假设支点位于分区末尾的第x个索引处；

K = x =>  pivot is the right answer
K < x =>  the answer is in the left partition, search left partition  
K > x =>  the answer is in the right partition, search right partition 

Answer 2

我在代码中发现了一个错误:在分区部分交换了两个元素之后，我移动了指针(left++，右-)，就像快速排序一样，但是应该是n。

谢谢你们的出席！