根据本文，在n个项目的列表中寻找第k个最大的项目，下面的算法在最坏的情况下将花费O(n)时间。

将数组分成n/5个列表，每个列表有5个元素。 求每个5个元素的子数组的中值。 递归地找到所有中位数的中位数，记作M 将数组划分为两个子数组第一个子数组包含大于M的元素，设这个子数组为a1，而其他子数组包含小于M的元素，设这个子数组为a2。 如果k <= |a1|，返回选择(a1,k)。 k−1 = |a1|，返回M。 如果k> |a1| + 1，返回选择(a2,k−a1−1)。

分析:如原文所述:

我们使用中位数将列表分成两部分(前一半， 如果k <= n/2，反之则为后半部分)。这个算法需要 对于某个常数c，递归第一级的时间cn/2 at 下一层(因为我们在大小为n/2的列表中递归)，cn/4在 第三层，以此类推。总时间为cn + cn/2 + cn/4 + ．．．． = 2cn = o(n)。

为什么分区大小是5而不是3?

如原文所述:

将列表除以5可以保证最坏情况下70−30的分割。至少 至少一半的中位数大于中位数的中位数 n/5块中的一半至少有3个元素，这就给出了a 3n/10的分割，这意味着另一个分区在最坏情况下是7n/10。 得到T(n) = T(n/5)+T(7n/10)+O(n)由于n/5+7n/10 < 1 最差情况运行时间isO(n)。

现在我尝试将上述算法实现为:

public static int findKthLargestUsingMedian(Integer[] array, int k) {
        // Step 1: Divide the list into n/5 lists of 5 element each.
        int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
        // Step 2: Find pivotal element aka median of medians.
        int medianOfMedian =  findMedianOfMedians(array, noOfRequiredLists);
        //Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
        List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
        List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
        for (Integer element : array) {
            if (element < medianOfMedian) {
                listWithSmallerNumbers.add(element);
            } else if (element > medianOfMedian) {
                listWithGreaterNumbers.add(element);
            }
        }
        // Next step.
        if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
        else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
        else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
        return -1;
    }

    public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
        int[] medians = new int[noOfRequiredLists];
        for (int count = 0; count < noOfRequiredLists; count++) {
            int startOfPartialArray = 5 * count;
            int endOfPartialArray = startOfPartialArray + 5;
            Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
            // Step 2: Find median of each of these sublists.
            int medianIndex = partialArray.length/2;
            medians[count] = partialArray[medianIndex];
        }
        // Step 3: Find median of the medians.
        return medians[medians.length / 2];
    }

为了完成，另一种算法利用优先队列，花费时间O(nlogn)。

public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
        int p = 0;
        int numElements = nums.length;
        // create priority queue where all the elements of nums will be stored
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // place all the elements of the array to this priority queue
        for (int n : nums) {
            pq.add(n);
        }

        // extract the kth largest element
        while (numElements - k + 1 > 0) {
            p = pq.poll();
            k++;
        }

        return p;
    }

这两个算法都可以被测试为:

public static void main(String[] args) throws IOException {
        Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
        System.out.println(findKthLargestUsingMedian(numbers, 8));
        System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
    }

如预期输出为: 18 18

Python中性感的快速选择

def quickselect(arr, k):
    '''
     k = 1 returns first element in ascending order.
     can be easily modified to return first element in descending order
    '''

    r = random.randrange(0, len(arr))

    a1 = [i for i in arr if i < arr[r]] '''partition'''
    a2 = [i for i in arr if i > arr[r]]

    if k <= len(a1):
        return quickselect(a1, k)
    elif k > len(arr)-len(a2):
        return quickselect(a2, k - (len(arr) - len(a2)))
    else:
        return arr[r]

A Programmer's Companion to Algorithm Analysis给出了一个O(n)的版本，尽管作者指出常数因子如此之高，您可能更喜欢简单的排序-列表-然后选择方法。

我已经回答了你的问题:)

c++标准库几乎完全有这个函数调用nth_element，尽管它确实会修改数据。它有线性运行时间，O(N)，它也做部分排序。

const int N = ...;
double a[N];
// ... 
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a

下面是一个随机化快速选择的c++实现。这个想法是随机选择一个主元。为了实现随机分区，我们使用一个随机函数rand()来生成l和r之间的索引，将随机生成索引处的元素与最后一个元素交换，最后调用以最后一个元素为枢轴的标准分区过程。

#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;

int randomPartition(int arr[], int l, int r);

// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method.  ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
    // If k is smaller than number of elements in array
    if (k > 0 && k <= r - l + 1)
    {
        // Partition the array around a random element and
        // get position of pivot element in sorted array
        int pos = randomPartition(arr, l, r);

        // If position is same as k
        if (pos-l == k-1)
            return arr[pos];
        if (pos-l > k-1)  // If position is more, recur for left subarray
            return kthSmallest(arr, l, pos-1, k);

        // Else recur for right subarray
        return kthSmallest(arr, pos+1, r, k-pos+l-1);
    }

    // If k is more than number of elements in array
    return INT_MAX;
}

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

// Standard partition process of QuickSort().  It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x) //arr[i] is bigger than arr[j] so swap them
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]); // swap the pivot
    return i;
}

// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
    int n = r-l+1;
    int pivot = rand() % n;
    swap(&arr[l + pivot], &arr[r]);
    return partition(arr, l, r);
}

// Driver program to test above methods
int main()
{
    int arr[] = {12, 3, 5, 7, 4, 19, 26};
    int n = sizeof(arr)/sizeof(arr[0]), k = 3;
    cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
    return 0;
}

上述解的最坏情况时间复杂度仍为O(n2)。在最坏的情况下，随机函数可能总是选择一个角元素。上述随机化QuickSelect的期望时间复杂度为Θ(n)

我实现了在n个未排序元素中寻找第k个最小值的动态规划，特别是竞赛方法。执行时间为O(n + klog(n))。所使用的机制在维基百科关于选择算法的页面上被列为方法之一(如上面的帖子之一所示)。你可以阅读算法，也可以在我的博客页面“查找k个最小值”上找到代码(java)。此外，逻辑可以对列表进行部分排序——在O(klog(n))时间内返回第一个K min(或max)。

虽然代码提供了第k个最小值的结果，但可以使用类似的逻辑来查找O(klog(n))中的第k个最大值，忽略创建比赛树的前期工作。