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

Question

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

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

该函数将a[]的第一个元素视为一个枢轴并重新排列数组，使得所有小于或等于枢轴的元素都在数组的左侧，所有大于该枢轴的元素枢轴位于右侧。此外，它移动枢轴，使枢轴成为左侧部分的最后一个元素。 return 值为左边的元素个数。

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

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 (___________);   
    }
}

缺少的参数列表分别是

(a, left_end, k) 和 (a+left_end+1, n-left_end-1, k-left_end-1)
(a, left_end, k) 和 (a, n-left_end-1, k-left_end-1)
(a, left_end+1, n-left_end-1, k-left_end-1) 和 (a, left_end, k)
(a, n-left_end-1, k-left_end-1) 和 (a, left_end, k)

我在这里找到了关于“How to find the kth largest element in an unsorted array of length n in O(n)?”

的很好的解释

我已阅读 partition , used in quick sort。答案是选项 (1)。我同意答案。但我需要正式的解释。

Can you explain little bit please ?

编辑：据我所知，分区算法将选定的枢轴放在正确的位置。我们需要递归分区算法来找到数组中的第 k 个最小元素。分区算法运行在数组的单边上，即排序轴的左侧或右侧。我被困在这里了。我在想，这取决于第 k 个索引号？

Answer 1

很简单。比如说，你选择了数组中最大的 q th 元素。在这种情况下，分区在左半部分有 q-1 个元素，在右半部分有 n-q 个元素，而 q th 个元素是枢轴。现在，3 种可能性：

如果 q 是 k，您就会得到答案，这就是您的 return 陈述。
如果q > k，则k th元素在数组的左半部分，并且，在左半部分，它是，仍然， k th 最大的元素。因此，在分区中，我们传递了数组的左半部分 k，我们必须在那里找到 k th 最大的元素。
如果q < k，那么，k th最大的元素在数组的右半部分。另外，由于有 q 个元素小于此右侧部分的最小元素，因此原始数组中的 k th 个最大元素在右侧数组中最大 k - q th 个。因此，我们传递正确的数组和 k-q，以找到分区的最大 k-q th 元素。

编辑：

为您的代码添加注释：

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 (___________);   
    }
}

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

Kth smallest element in an array using partition

c

arrays

algorithm

partitioning

data-structures