堆排|快排合集

JavaScript快速排序

方法二（原地快排）：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    const sort=(arr,left,right)=>{
        if(left>=right) return;//判断终止条件
        let pi=partition(arr,left,right);//切分数组的中间下标
        //递归
        sort(arr,left,pi-1);
        sort(arr,pi+1,right);

    }
    sort(nums,0,nums.length-1);
    return nums;
};

function partition(arr,left,right){
    let pivot=arr[left];//以left为基准
    let i=left+1,j=right;//双指针，i之前的数都比pivot小，j之后的大
    while(i<=j){//注意判断i==j，结合例子，如1，2，i和j都指向2时j还会--
        while(i<right && arr[i]<=pivot)//找第一个比pivot大的数
        {
            i++;//小的则跳过，while结束时nums[i]大于pivot
        }
        while(j>left && arr[j] > pivot){//找比pi小的数
            j--;
        }
        if(i>=j){//判断终止条件，结合具体用例来判断容易理解
            break;
        }
        swap(arr,i,j);//交换i与j

    }
    swap(arr,left,j);//将pivot与j换，pi左边元素小，右边大
    return j;//返回j的下标

}

function swap(arr,i,j){
    let temp=arr[j];
    arr[j]=arr[i];
    arr[i]=temp;
}

排序算法|堆排序

215. 数组中的第K个最大元素

方法1：堆排序，时间复杂度klogn

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var len;
var findKthLargest = function(nums, k) {
    buildMaxHeap(nums);//构建大顶堆
    for(let i=nums.length-1,j=0;j<k;i--,j++){
        swap(nums,i,0);//首尾交换，取出最大值放到末尾
        len--;//注意len值
        heapify(nums,0)//交换后堆化
    }
    console.log(nums);
    return nums[nums.length-k];
};

function buildMaxHeap(arr){
    len=arr.length;//在此给全局变量len赋值
    for(let i=Math.floor(len/2);i>=0;i--)//最后一个非子结点
    {
        heapify(arr,i);
    }

}

function heapify(arr,i){
    let left=i*2+1;
    let right=i*2+2;
    let largest=i;
    if(left<=len-1 && arr[left]>arr[largest]){
        largest=left;
    }
    if(right<=len-1 && arr[right]>arr[largest]){
        largest=right;
    }
    if(largest!=i){
        swap(arr,i,largest);
        heapify(arr,largest);
    }

}

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

方法2：

快排，时间复杂度可达O（n）

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var len;
var findKthLargest = function(nums, k) {
    let left=0,right=nums.length-1;
    k=nums.length-k;//转成排名第n-k的索引
    while(left<=right){
        let pi=partition(nums,left,right);
        if(pi>k){
            right=pi-1;
        }
        else if(pi<k){
            left=pi+1;
        }
        else return nums[pi];
    }

};



function partition(arr,left,right){
    let pivot=arr[left];//以left为基准
    let i=left+1,j=right;//双指针，i之前的数都比pivot小，j之后的大
    while(i<=j){//注意判断i==j，结合例子，如1，2，i和j都指向2时j还会--
        while(i<right && arr[i]<=pivot)//找第一个比pivot大的数
        {
            i++;//小的则跳过，while结束时nums[i]大于pivot
        }
        while(j>left && arr[j] > pivot){//找比pi小的数
            j--;
        }
        if(i>=j){//判断终止条件，结合具体用例来判断容易理解
            break;
        }
        swap(arr,i,j);//交换i与j

    }
    swap(arr,left,j);//将pivot与j换，pi左边元素小，右边大
    return j;//返回j的下标

}

function swap(arr,i,j){
    let temp=arr[j];
    arr[j]=arr[i];
    arr[i]=temp;
}

https://mp.weixin.qq.com/s/8ZTMhvHJK_He48PpSt_AmQ

https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484495&idx=1&sn=bbfeba9bb5cfd50598e2a4d08c839ee9&scene=21#wechat_redirect