使用
sort()将数组从大到小排序，输出第arr[k-1]的值，时间复杂度为O(nlgn)-
时间复杂度为
O(n)
思想：利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
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);
