# js sort and select

• ### Random Selection Algorithm Based on Quick Sorting

``````/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function (nums, k) {
function getKth(nums, start, end, k) {
let random = Math.floor(Math.random() * (end - start + 1)) + start,
curIndex = start,
i = start + 1,
j = end,
temp = 0

temp = nums[start]
nums[start] = nums[random]
nums[random] = temp

while (true) {
while ((nums[i] <= nums[curIndex]) && (i < j)) {
i++
}
while (nums[j] > nums[curIndex]) {
j--
}

if (i >= j) {
break
}
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
temp = nums[start]
nums[start] = nums[j]
nums[j] = temp

if (k === j) {
return nums[j]
} else if (k > j) {
return getKth(nums, j + 1, end, k)
} else {
return getKth(nums, start, j - 1, k)
}
}

return getKth(nums, 0, nums.length - 1, nums.length - k)
}
``````

The average complexity is O(n)

### Selection Algorithm Based on Quick Sort

``````/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function (nums, k) {
function getKth(nums, start, end, k) {
let curIndex = start,
i = start + 1,
j = end,
temp = 0

while (true) {
while ((nums[i] <= nums[curIndex]) && (i < j)) {
i++
}
while (nums[j] > nums[curIndex]) {
j--
}

if (i >= j) {
break
}
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
temp = nums[start]
nums[start] = nums[j]
nums[j] = temp

if (k === j) {
return nums[j]
} else if (k > j) {
return getKth(nums, j + 1, end, k)
} else {
return getKth(nums, start, j - 1, k)
}
}

return getKth(nums, 0, nums.length - 1, nums.length - k)
}
``````

The average complexity is O(nln(n))

### Use Quick Sort

``````/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
nums.sort((x, y) => (
y - x
))
return nums[k - 1]
}
``````

The complexity is O(nln(n))

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.