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

我想要一个更快的函数来在C#中找到第N个最大数量的Int数组.此函数采用N和Array并返回该数字的索引.

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

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)

小智.. 29

随机快速选择算法适用于平均情况复杂度O(n).实际上,很少有O(n ^ 2).它使用quicksort的分区功能

1> 小智..：

---

随机快速选择算法适用于平均情况复杂度O(n).实际上,很少有O(n ^ 2).它使用quicksort的分区功能

---

[维基百科上的QuickSelect](https://en.wikipedia.org/wiki/Quickselect)和[此处的C#实现](http://rosettacode.org/wiki/Quickselect_algorithm)

2> Harald Coppo..：

---

如果你的阵列有一个数字大小,你需要第五大数字,那么你正在排序许多你不需要的数字.

保持长度为n的升序排序序列(链表？)并不是更快,并检查每个元素是否大于第一个(升序中最小的)

如果更小:跳到大型数组中的下一个元素

如果更大:从排序数组中删除最小的一个,这是第一个元素,并将较大的元素插入适当的位置,保持数组排序.

扫描完整数组后,排序序列中的第一个元素就是您要查找的元素.

大多数比较仅与排序数组的第一个元素有关.你必须N次更改数组,N次最大数字一次.更改数组是删除第一个元素(最小的)并找到插入新元素的位置以保持数组排序

更正:我声明数组必须更改N次是不正确的.当提供按升序排序的数组时,最容易看到这一点:每个比较的数字将大于N-size数组中的最小数字,从而导致替换

---

我想指出一个排序的链表是过度的.大小为N的最小堆(堆头比所有其他元素小)足以选择N个最大元素,并且它的头部是第N个最大的元素,它正好回答了这个问题.即使您希望最后排序的N个最大元素,最好在选择期间继续使用最小堆,因为堆通常需要的维护少于排序列表.

---

@MatthieuM.建议使用min-heap将其驱动为O(n log(N)).

3> Domysee..：

---

这将是@ HaraldDutch答案的实施.

int get(int[] array, int n)
{
    var comparer = Comparer.Create((x, y) => array[x].CompareTo(array[y]));    //compare the array entries, not the indices
    var highestIndices = new SortedSet(comparer);
    for (var i = 0; i < array.Length; i++)
    {
        var entry = array[i];
        if (highestIndices.Count < n) highestIndices.Add(i);
        else if (array[highestIndices.Min] < entry)
        {
            highestIndices.Remove(highestIndices.Min);
            highestIndices.Add(i);
        }
    }

    return highestIndices.Min;
}

你必须传入1而不是0.

4> kain64b..：

---

你需要使用选择算法 https://en.wikipedia.org/wiki/Selection_algorithm

这里有漂亮的幻灯片:https://c3p0demo.googlecode.com/svn/trunk/scalaDemo/script/Order_statistics.ppt 一般算法:

Select(A,n,i):
    Divide input into ?n/5? groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ?n/5?, ?n/10?)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

5> 小智..：

---

您可以创建一个大小为N的堆,其中第一个元素的编号最大(与通常给出的最小元素相对).然后,您将遍历整数数组,只要您的元素小于堆的最大成员,就可以将其插入堆中.如果这使得堆超过N的大小,则删除其中的最大成员.

这应该是最便宜的方法之一.特定的"第n个最大的m"算法可能会击败它,但可能不是渐近的.

6> gnasher729..：

---

您的排序算法到目前为止并不是最快的.你应该google for"Quicksort"获得更快,更快的算法.

在你实现了Quicksort之后,你会考虑是否真的需要对整个数组进行排序.假设您想要找到10,000个数字中最大的20个,为什么要对剩余的9,980个数字进行排序？您可以轻松修改Quicksort,以便找到N个最大的数字,但大部分时间忽略其余数字.