使用快速排序的第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