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

Question

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

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

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

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

缺少的参数列表分别是

1. (a, left_end, k) 和 (a+left_end+1, n-left_end-1, k-left_end-1)
2. (a, left_end, k) 和 (a, n-left_end-1, k-left_end-1)
3. (a, left_end+1, n-left_end-1, k-left_end-1) 和 (a, left_end, k)
4. (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 ，用于 quick sort .答案为选项(1)。我同意答案。但我需要正式的解释。

Can you explain little bit please ?

---

编辑:据我所知，分区算法将所选的枢轴放在正确的位置。我们需要递归分区算法来查找数组中的第 k 个最小元素。分区算法在数组的一侧运行，无论是在已排序的主元的左侧还是右侧。我被困在这里了。我在想，这取决于第k个索引号？

Answer 1

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

• 如果q是 k ，您会得到答案，即您的返回声明。
• 如果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 (___________);   
    }
}