冒泡排序
var findKthLargest = function(nums, k) {
for(let i = 0;i < nums.length - 1;i++){
for(let j = 0; j < nums.length - i - 1;j++){
if(nums[j] > nums[j+1]){
var temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
nums.reverse();
return nums[k-1];
};
选择排序
var findKthLargest = function(nums, k) {
for(let i = 0;i < k;i++){
var max = nums[i];
let n = i;
for(let j = i + 1; j < nums.length+1;j++){
if(nums[j] > max){
max = nums[j];
n = j;
}
}
if(n != i){
let temp = nums[i];
nums[i] = nums[n];
nums[n] = temp;
}
}
console.log(nums);
return nums[k-1];
};
一行代码
var findKthLargest = function(nums, k) {
return nums.sort((a,b)=>b-a)[k-1]
};
相当于调用
function sortNumber(a,b)
{
return a - b
}
arr.sort(sortNumber)
sort() 方法用于对数组的元素进行排序,并返回数组。默认排序顺序是根据字符串Unicode，不是unicode是ascii。sort方法用于根据一定条件对数组元素进行排序。如果调用sort()方法时没有传递参数，则按字母顺序对数组中的元素进行排序；如果提供一个函数参数，则根据该函数提供的顺序来对数组中的元素进行排序。
- 若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。
- 若 a 等于 b，则返回 0。
- 若 a 大于 b，则返回一个大于 0 的值。
其实就是比较函数两个参数a和b，返回a-b 升序，返回b-a 降序。
堆栈法
构造前 k 个最大元素小顶堆，取堆顶
我们也可以通过构造一个前 k 个最大元素小顶堆来解决，小顶堆上的任意节点值都必须小于等于其左右子节点值，即堆顶是最小值。
所以我们可以从数组中取出 k 个元素构造一个小顶堆，然后将其余元素与小顶堆对比，如果大于堆顶则替换堆顶，然后堆化，所有元素遍历完成后，堆中的堆顶即为第 k 个最大值
具体步骤如下：
从数组中取前 k 个数（ 0 到 k-1 位），构造一个小顶堆
从 k 位开始遍历数组，每一个数据都和小顶堆的堆顶元素进行比较，如果小于堆顶元素，则不做任何处理，继续遍历下一元素；如果大于堆顶元素，则将这个元素替换掉堆顶元素，然后再堆化成一个小顶堆。
遍历完成后，堆顶的数据就是第 K 大的数据
let findKthLargest = function(nums, k) {
let heap = [,], i = 0
while(i < k) {
heap.push(nums[i++])
}
buildHeap(heap, k)
for(let i = k; i < nums.length; i++) {
if(heap[1] < nums[i]) {
heap[1] = nums[i]
heapify(heap, k, 1)
}
}
return heap[1]
};
let buildHeap = (arr, k) => {
if(k === 1) return
for(let i = Math.floor(k/2); i>=1 ; i--) {
heapify(arr, k, i)
}
}
let heapify = (arr, k, i) => {
while(true) {
let minIndex = i
if(2*i <= k && arr[2*i] < arr[i]) {
minIndex = 2*i
}
if(2*i+1 <= k && arr[2*i+1] < arr[minIndex]) {
minIndex = 2*i+1
}
if(minIndex !== i) {
swap(arr, i, minIndex)
i = minIndex
} else {
break
}
}
}
let swap = (arr, i , j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
快速排序
快速选择（quickselect）算法
无论是排序算法还是构造堆求解 Top k问题，我们都经过的一定量的不必要操作：
如果使用排序算法，我们仅仅想要的是第 k 个最大值，但对其余不需要的数也进行了排序
如果使用堆排序，需要维护一个大小为 k 的堆(大顶堆，小顶堆)，时间复杂度也为 O(nlogk)
快速选择（quickselect）算法与思路上相似，我们先看看是如何实现的？
使用了分治策略的思想，所谓分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。
过程：
首先从序列中选取一个数作为基准数
将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边 （一次partition）
然后分别对基准的左右两边重复以上的操作，直到数组完全排序
具体按以下步骤实现：
- 创建两个指针分别指向数组的最左端以及最右端
- 在数组中任意取出一个元素作为基准
- 左指针开始向右移动，遇到比基准大的停止
- 右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
- 重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边
- 然后分别对基准的左右两边重复以上的操作，直到数组完全排序
注意这里的基准该如何选择：最简单的一种做法是每次都是选择最左边的元素作为基准，但这对几乎已经有序的序列来说，并不是最好的选择，它将会导致算法的最坏表现。还有一种做法，就是选择中间的数或通过 Math.random() 来随机选取一个数作为基准，下面的代码实现就是以随机数作为基准
var findKthLargest = function (nums, k) {
let start = 0, end = nums.length - 1;
let key = nums.length - k;
while (true) {
let i = partition(nums, start, end);
if (i === key) {
return nums[key];
} else if (i < key) {
start = i + 1;
} else {
end = i - 1;
}
}
};
function partition(arr, start, end) {
if (end > start) {
swap(arr, start, start + Math.floor((end - start) / 2));
}
let pivot = arr[start], j = start;
for (let i = start + 1; i <= end; i++) {
if (arr[i] < pivot) {
if(++j === i) continue
swap(arr, i, j);
}
}
swap(arr, start, j);
return j;
}
function swap(ary, i, j) {
let temp = ary[i];
ary[i] = ary[j];
ary[j] = temp;
}
|