算法通关村-----快速排序的应用

这篇具有很好参考价值的文章主要介绍了算法通关村-----快速排序的应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数组中的第K个最大元素

问题描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。详见leetcode215

问题分析

之前我们已经使用堆排序/堆查找的方式解决了这个问题。详见堆在查找和排序中的应用找到数组中的第K个最大元素，最直接的方式就是使用快速排序使数组有序，之后返回数组的第K个元素，当然可以使用快速排序来实现了，其实只要是需要数组有序，都可以通过快排来实现，因为快速排序相对高效。比如找最值，二分查找也需要数组有序等。

代码实现

可以使用快速排序的原理和实现中任一方式实现快速排序

public int findKthLargest(int[] nums, int k) {
    quickSort(nums,0,nums.length-1);
    return nums[k-1];
}

public void quickSort(int[] nums,int left,int right){
    if(left>=right){
        return;
    }
    int pivot = nums[right];
    int i = left-1;
    for(int j=left;j<right;j++){
        if(nums[j]>pivot){
            i++;
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
    }
    int pivotIndex = i+1;
    int temp = nums[right];
    nums[right] = nums[pivotIndex];
    nums[pivotIndex] = temp;
    quickSort(nums,left,pivotIndex-1);
    quickSort(nums,pivotIndex+1,right);
}