谁能解释我做错了什么？我想找到第 k 个最小的元素但是出了点问题）
示例：我有未排序的数组 int[] uA = { 2, 9, 4, 13, 11, 7, 8 }; 我将“9”作为枢轴元素，在第一次分区（快速排序）迭代后，我将拥有这个数组 {2、8、4、7、11、13、9}。中间指针将显示在“11”处。这到底意味着什么？并非所有元素都对 11 大于 11。而且 11 根本不在“正确的位置”。但是，例如，我想返回第 5 个最小的元素（11）。
问问题
1300 次
2 回答
1
枢轴不在正确的位置，您应该在分区结束时将枢轴放在正确的位置以找出枢轴的位置。（你真的不需要关心中间元素）然后你可以使用这个信息来计算第K个最小的元素。假设主元在分区结束时位于第 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
于 2012-11-01T21:22:03.970 回答
0
我在我的代码中发现了一个错误：在分区部分交换两个元素后，我像快速排序一样移动了指针（left++，right--），但不应该。
谢谢大家的关注！
于 2012-11-02T11:50:53.447 回答