使用分区的数组中的第k个最小元素

提问者：小点点

使用分区的数组中的第k个最小元素

假设在C编程语言中为您提供了以下函数声明。

int partition(int a[], int n);

该函数将的第一个元素视为一个枢轴，并重新排列数组，使小于或等于该枢轴的所有元素都在数组的左侧部分，而大于该枢轴的所有元素都在右侧部分。此外，它移动枢轴，以便枢轴是左侧部分的最后一个元素。返回值是左边部分的元素数。

C编程语言中的以下部分给定函数用于使用分区函数查找大小为n的数组中的第k个最小元素。我们假设。

int kth_smallest (int a[], int n, int k)
{
    int left_end = partition (a, n);
    if (left_end+1==k) {
        return a[left_end];
    }
    if (left_end+1 > k) {
        return kth_smallest (___________);
    } else {
        return kth_smallest (___________);   
    }
}

缺少的参数列表分别是

和和

和

我在这里找到了一个很好的解释，关于“如何在一个长度为n的未排序数组中找到第k个最大的元素？”

我已经阅读了快速排序中使用的分区。答案是选项（1）。我同意答案。但我需要正式的解释。

你能解释一下吗？

编辑:AFAIK，分区算法将选择的枢轴放在正确的位置。我们需要递归分区算法来寻找数组中的第k个最小元素，分区算法运行在数组的单侧，可以是它的排序枢轴的左侧，也可以是它的排序枢轴的右侧。我被困在这里了。我在想，这取决于第k个指数？

共1个答案

匿名用户

很简单。例如，您选择数组中最大的一个元素。在这种情况下，partition的左半部分有元素，右半部分有元素，而元素是枢轴。现在，有三种可能性:

是，则得到答案，即返回语句。/li> ；k/code>，则元素位于数组的左半部分，而在左半部分，它仍然是最大的元素。因此，在分区中，我们传递数组的左半部分和，我们必须在其中找到最大的元素。/li> ，则数组右半部分中的最大元素。另外，由于有元素小于该右数组的最小元素，因此原始数组中的最大元素是右数组中的最大元素。因此，我们传递右数组和，以查找分区的最大元素。/li>

编辑:

向代码中添加注释:

int partition(int a[], int n);    //breaks array into 2 parts, according to pivot (1st element of array), left is smaller and right is larger han pivot.

现在，你的递归算法:

int kth_smallest (int a[], int n, int k)
{
    int left_end = partition (a, n);    //get index of a[0] in sorted array a
    if (left_end+1==k) {           //kth largest element found
        return a[left_end];
    }
    if (left_end+1 > k) {     //k th largest element in left part of array, and is k th largest in the left part
        return kth_smallest (___________);
    } else {                  ////k th largest element in right part of array, and is (k - left_end) th largest in the right part
        return kth_smallest (___________);   
    }
}