查找使用分区列表中的第K个最小的元素 - 帮助我理解

Question

好吧，我有一个任务找到使用几种不同的方法列表中的第K个最小元素....

第一种方法是对列表进行排序，然后返回第K个最小元素。容易，我的心态是说列表= 10个元素，排序列表按升序排列，然后在第10位返回元素

下一个方法使用快速排序的分区：

“第二种算法是应用Quicksort中使用的分区程序该过程对数组进行分区，以便所有小于某个数据透视表元素的元素都位于数组之前，并且所有大于该数据透视表元素的元素都位于数组之后。我们可以通过分区来解决选择问题，直到数据项位于第k个时隙为止，如果k小于pivotposition，则递归地划分左侧子数组，并且通过递归地划分右侧子数据库ay如果k大于pivotposition。 。当k = pivotposition，我们完成”

说我有10项的列表：

3 8 9 2 4 5 1 7 10 6，其中5是枢转..我知道我通常将具有2个阵列

3 2 4 1和8 9 7 10 6

，但我不理解的是：“我们可以通过分区解决选择问题，直到枢轴产品在第k个插槽“。

什么是第k个插槽？对我来说，我一直在想，kth =数组的长度，所以在这种情况下，10.其中有6个值，这显然不是最低的......并且是不正确的。

有人可以使用这个样本数组，只是告诉我这个算法的含义是什么，以及它如何找到第k /最小的元素？谢谢

Answer 1

我认为你已经以复杂的方式寻找解决方案。

这是你如何找到使用QuickSort的第k个最小的元素（很好，不完全快速排序，我会告诉为什么）。

在快速排序中，您选择一个随机数据透视元素，并将整个数组分为两部分，并递归排序左侧和右侧的子数组以形成整个已排序的数组。

在这个问题中，你不必这样做。你正在做的是，

1. 选择一个随机数据元素。
2. 用[Sub-array 1] Pivot [Sub-array2]划分数组，其中子数组1的元素少于pivot，子数组2的元素大于pivot的 。
3. 检查子数组1的大小。

If it is, 
     a.Greater than 'k' then your kth element lies in the first sub-array. Go recursively. Start sorting the sub-array1 alone and you can entirely discard the sub-array2 as you can be sure that 'kth' element cannot occur at a position greater than k! Repeat step-1 for the right sub-array 
     b.Lesser than 'k' then your kth element lies in the second sub-array. Again do as said above. Repeat step-1 for left subarray. 
     c.If the size of sub-array1 is k-1 then your pivot element must be the kth largest element in your array.Bingo! you have your 'kth' largest element in the array 

因此，要解决您的疑问，

在这里你是不是排序整个数组，但只有 它的一部分（甚至是不完全正确的。你会得到它如果你完全了解我的上述解释。）

Answer 2

在Quicksort中，一旦你的轴心位置是k，左边的所有东西都会减少，而右边的东西也会更大，所以如果你只需要第k个值就不需要继续排序。