使用快速排序的第k個最小數字

Question

我有以下分區方法和kthsmallest方法（快速排序的變化），它適用於某些情況，但在某些情況下爲我提供值32767。

void swap(int* a, int* b){ 

int temp = *b; 
*b = *a; 
*a = temp; 
} 

int partition(int* arr, int l, int r){ 

int pivot = arr[r]; 
int i = l, j=0; 

for(j=l; j<=r-1; j++){ 
    if(arr[j] <= pivot){ 
     swap(&arr[i], &arr[j]); 
     i++; 
    } 
} 

swap(&arr[i], &arr[j]); 
return i; 
} 

而且kthsmallest功能如下： -

int kthsmallest(int* arr, int low, int high, int k){ 
/* low = 0 and high = #elements - 1 */ 
/* k is in between 1 to high + 1 */ 

if (k>0 & k<=high-low+1)  { 
    // pos is partitioning index, arr[p] is now at right place 
    int pos = partition(arr, low, high); 

    // Separately sort elements before/partition and after partition 

    if(pos-low == k-1){ 
      return arr[pos]; 
    } 
    //if position returned is greater than k, recurse left subarray 
    else if(pos-low > k-1){ 
      return kthsmallest(arr, low, pos-1, k); 
    } 

    return kthsmallest(arr, pos+1, high, k-(pos+1)); 

} 
} 

然而，當我改變kthsmallest函數最後一次通話即

更改工作：return kthsmallest(arr, pos+1, high, k-(pos+1));

要：return kthsmallest(arr, pos+1, high, k-(pos+1)+low);

我想要你理解爲什麼我需要增加低到k-（pos + 1）。因爲在我看來，當遞歸進入右側的子數組時，大數組中第k個最小數字歸結爲k - 最後一個分區元素-1，即k-（pos + 1）。

Answer 1

您需要low，因爲當您遞歸地從一個新數組開始時，low將成爲pos的參考。所以新的k將從low至pos計算。

也許一個例子會更清晰。

讓我們找到這個數組的第9個最小元素：

現在我們做的分區，所以我們得到：

從pos向左我們在拿到了最小的元素數組，這是3個最小的元素。現在我們將使用從pos+1開始的子數組。而我們需要獲得第六最小的元素：

我們做了分區在這個子陣：

記住，我們是在一個子陣列的工作試圖找到第六最小元素。在這種情況下，我們將子數組中的第012個最小元素分開。因此，我們的新k將是： 我們做一個新的分區： 現在我們超過了最後一個子數組的第4個最小元素，所以我們修剪的最後一部分： 我們再做分區：

而我們得到：

因此，我們的數量是17。

希望它有幫助。

PD：正如David C. Rankin在評論中所說，您可能應該更改&爲&&。

Answer 2

看來的你有試圖硬塞進一個quickselect例行成遞歸功能時，有沒有理由使函數的遞歸開始與問題之一。您只需確定'k'元素所在的分區，就不需要排序。所有您需要爲您kthsmallest是：

/** select the ZERO BASED 'k' element from 'arr'. 
* where 'low' and 'high' are the ZERO BASED low 
* and high indexes for 'arr'. 
*/ 
int kthsmallest (int *arr, int low, int high, int k) 
{ 
    for (;;) { 
     if (low == high) 
      return arr[low]; 

     int pos = partition (arr, low, high); 

     if (k == pos) 
      return arr[k]; 
     else if (k < pos) 
      high = pos - 1; 
     else 
      low = pos + 1; 
    } 
} 

使用您的確切partition和swap功能，你可以寫一個小例子程序來測試k在一個陣列的每個元素。 （注：是基於零索引ķ，例如第一最小元件從所述陣列的末端偏移零返回的元素 - 就像在C的其餘部分）

#include <stdio.h> 

void swap (int *a, int *b); 
int partition (int *arr, int l, int r); 

/** select the ZERO BASED 'k' element from 'arr'. 
* where 'low' and 'high' are the ZERO BASED low 
* and high indexes for 'arr'. 
*/ 
int kthsmallest (int *arr, int low, int high, int k) 
{ 
    for (;;) { 
     if (low == high) 
      return arr[low]; 

     int pos = partition (arr, low, high); 

     if (k == pos) 
      return arr[k]; 
     else if (k < pos) 
      high = pos - 1; 
     else 
      low = pos + 1; 
    } 
} 

int main (void) { 

    int a[] = { 51, 86, 34, 79, 92, 68, 14, 47, 22, 6 }, 
     nelem = sizeof a/sizeof *a; 

    for (int i = 0; i < nelem; i++) 
     printf (" nth (%2d) element is : %d\n", i, 
       kthsmallest (a, 0, nelem - 1, i)); 

    return 0; 
} 

void swap (int *a, int *b) 
{ 
    int temp = *b; 
    *b = *a; 
    *a = temp; 
} 

int partition (int *arr, int l, int r) 
{ 
    int pivot = arr[r]; 
    int i = l, j = 0; 

    for (j = l; j <= r - 1; j++) { 
     if (arr[j] <= pivot) { 
      swap (&arr[i], &arr[j]); 
      i++; 
     } 
    } 

    swap (&arr[i], &arr[j]); 

    return i; 
} 

實施例使用/輸出

$ ./bin/kthsmall 
nth (0) element is : 6 
nth (1) element is : 14 
nth (2) element is : 22 
nth (3) element is : 34 
nth (4) element is : 47 
nth (5) element is : 51 
nth (6) element is : 68 
nth (7) element is : 79 
nth (8) element is : 86 
nth (9) element is : 92