无序数组中找第k大的数

1. 使用sort()将数组从大到小排序，输出第arr[k-1]的值，时间复杂度为O(nlgn)

2. 时间复杂度为O(n)
   思想：利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

   1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

   2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。

时间复杂度近似为O(n)。

image.png

// 先一遍快速排序，再分三种情况
function sort(arr, low, hight) {
    var pivot = arr[low]
    var i = low, j = hight
    while (i < j) {
        while (arr[j] > pivot && i < j) --j
        while (arr[i] < pivot && i < j) ++i
        if (i < j) [arr[i], arr[j]] = [arr[j], arr[i]]
    }
    return i
}
function select(arr, low, high, k) {
    if (low === high) return arr[low]
    var index = sort(arr, low, high)//划分界限的下标，左边的都小，右边的都打
    var n = high - index + 1//当前的数是第几大
    if (n === k) {
        console.log(arr[index]);
    }
    else if (n < k) {
        select(arr, low, index - 1, k - n)//从左边找第k-n大的数
    } else {
        select(arr, index + 1, high, k)//从右边找第K大的数
    }
}
var arr = [6, 4, 3, 7, 5, 1, 9, 8]
select(arr, 0, arr.length - 1, 3);