algorithm - 第K个最大数字，为什么此运行时为O(n)而不是O(nlogn)

我在Leetcode遇到了第k个最大的问题
输入：[3,2,1,5,6,4]和k=2，输出：5
建议的解决方案：

 public int findKthLargest(int[] nums, int k) {
    shuffle(nums);
    k = nums.length - k;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo < hi) {
        final int j = partition(nums, lo, hi);
        if(j < k) {
            lo = j + 1;
        } else if (j > k) {
            hi = j - 1;
        } else {
            break;
        }
    }
    return nums[k];
}

private int partition(int[] a, int lo, int hi) {

    int i = lo;
    int j = hi + 1;
    while(true) {
        while(i < hi && less(a[++i], a[lo]));
        while(j > lo && less(a[lo], a[--j]));
        if(i >= j) {
            break;
        }
        exch(a, i, j);
    }
    exch(a, lo, j);
    return j;
}

private void exch(int[] a, int i, int j) {
    final int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

private boolean less(int v, int w) {
    return v < w;
}

分区不取o（n），主函数中的while循环不取o（logn），所以应该是o（nlogn）？这看起来像是使用了快速排序，但是快速排序的运行时是O（nlogn）如果quicksort取O（n），这是有意义的，但不是请帮助我了解发生了什么事？

最佳答案

这是一个随机算法，具有平均/预期的o（n）运行时。这是因为在随机洗牌输入列表之后，我们通常有足够好的支点，在每次分区函数调用之后，如果找不到目标，我们会将列表（下一步搜索）大约减少一半这意味着即使我们运气不好，不得不不断地调用分区函数，我们也会不断地将列表的大小减少一半，因此平均运行时间仍然只有o（n），因为o（n）+o（n/2）+o（n/4）+…+O（1）仍然是O（n）。

关于algorithm - 第K个最大数字，为什么此运行时为O(n)而不是O(nlogn)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50939049/