查找使用分區列表中的第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個值就不需要繼續排序。