c# - 找到 INT 数组的第 N 个最大数的最快方法是什么？

Question

我想要一个更快的函数来查找 C# 中 Int 数组的第 N 个最大数。此函数接受 N 和数组并返回该数字的索引。

这是我已经拥有的。它只是对数组进行排序，然后返回该数字的索引。 它完美地工作但我不确定这是否是最快的方法。没有完全排序的算法似乎是合乎逻辑的。

static int myFunction(int[] array, int N){
    int[] indexes = new int[array.Length];
    for (int i = 0; i < indexes.Length; i++)
        indexes[i] = i;

    for (int i = 0; i < array.Length; i++)
    {
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[i] < array[j])
            {
                int m = array[j];
                array[j] = array[i];
                array[i] = m;

                m = indexes[j];
                indexes[j] = indexes[i];
                indexes[i] = m;
            }
        }
    }
    return indexes[N];
}

一些结果:

myFunction(new int[] { 1, 3, 2, 0, 10 }, 0); //returns 4 (index of 10)
myFunction(new int[] { 1, 3, 2, 0, 10 }, 1); //returns 1 (index of 3)
myFunction(new int[] { 1, 3, 2, 0, 10 }, 2); //returns 2 (index of 2)

Answer 1

随机快速选择算法在平均案例复杂度 O(n) 下工作。实际上，O(n^2) 是非常罕见的。它使用了快速排序的分区功能