[数据结构与算法]leetcode215题--数组中的第K个最大元素（JS排序方法大全）

冒泡排序

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) {
    // 从 nums 中取出前 k 个数，构建一个小顶堆
    let heap = [,], i = 0
    while(i < k) {
       heap.push(nums[i++]) 
    }
    buildHeap(heap, k)
    
    // 从 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）
然后分别对基准的左右两边重复以上的操作，直到数组完全排序
具体按以下步骤实现：

1. 创建两个指针分别指向数组的最左端以及最右端
2. 在数组中任意取出一个元素作为基准
3. 左指针开始向右移动，遇到比基准大的停止
4. 右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
5. 重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边
6. 然后分别对基准的左右两边重复以上的操作，直到数组完全排序
   注意这里的基准该如何选择：最简单的一种做法是每次都是选择最左边的元素作为基准，但这对几乎已经有序的序列来说，并不是最好的选择，它将会导致算法的最坏表现。还有一种做法，就是选择中间的数或通过 Math.random() 来随机选取一个数作为基准，下面的代码实现就是以随机数作为基准

var findKthLargest = function (nums, k) {
    let start = 0, end = nums.length - 1;
    // 排好序后，数组中第key个元素就是第K大的元素
    let key = nums.length - k;
    while (true) {
        let i = partition(nums, start, end);
        if (i === key) {
            return nums[key];
        } else if (i < key) {
            // 说明要找的值比nums[i]要大，所以要在[i+1, end]中继续切分
            start = i + 1;
        } else {
            // 说明要找的值比nums[i]要小，所以要从[0, i-1]中继续切分
            end = i - 1;
        }
    }
};
function partition(arr, start, end) {
    // 找出中间值与起始值交换位置，再用起始值做pivot值，防止顺序数组与倒序数组。
    if (end > start) {
        swap(arr, start, start + Math.floor((end - start) / 2));
    }
    // j 记录pivot值最终在数组中的索引（也表示比pivot小的元素的个数）
    let pivot = arr[start], j = start;
    
    // 从start+1开始到end结束
    for (let i = start + 1; i <= end; i++) {
        // 将比pivot小的都放到pivot前面去
        if (arr[i] < pivot) {
            // 当有一个比pivot小的值就将pivot值最终索引j + 1
            if(++j === i) continue // 如果j+1 后与i相等，则直接跳过，索引相同不需要交换
            swap(arr, i, j);
        }
    }
    // 循环完了之后，索引j和j之前的元素都是比pivot小的，j就是pivot所在数组中最终的索引
    // 循环完成后交换pivot和arr[j]的位置
    swap(arr, start, j);
    return j;
}
function swap(ary, i, j) {
    let temp = ary[i];
    ary[i] = ary[j];
    ary[j] = temp;
}