Quick Sort-Find the Kth largest number in the array (from shallow to deep, the four methods are compared and explained!)

Finding the K-th largest number in an array is a question that is often tested in interviews with large factories. Some clever ghosts use sort() to sort directly, and two lines of code are used to solve it. This seems feasible, but in fact it falls into the trap of the person who asked the question. . What the interviewer wants to see is your understanding of the algorithm, not the function call. Below, I will take this question as an example, from the shallower to the deeper, using four methods to solve this problem, the last recommended is the quick sort , here is a dynamic demonstration diagram of the quick sort, the specific ideas and implementation are detailed in the article !
Insert picture description here

Article Directory


Topic: Finding the Kth largest

Insert picture description here

Method 1: Global Sort

Use the built-in function sort in C++ to perform global sorting, and then take the Kth largest value:

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        sort(a.begin(), a.end());
        return a[n-K];
    }
};

Submit result:

Insert picture description here

Method 2: local sort

Using the idea of ​​bubble sorting, each time the largest value is placed at the end of the array, until the Kth, the time complexity is O(nk):

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        for(int i=0; i<K; ++i)
        {
            for(int j=0; j<n-i-1; ++j)
            {
                if(a[j]>a[j+1])
                {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
        return a[n-K];
    }
};

Submit result:

Insert picture description here

Method Three: Priority Queue

The minimum heap is implemented. For the relationship between heap and priority queue, please refer to: heap and priority queue

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        priority_queue <int, deque<int>, greater<int>> nums; //队首最小,从小到大排序
        for(int i=0; i<n; ++i)
        {
            if(i<K)
            {
                nums.push(a[i]);
            }
            else
            {
                if(a[i]>nums.top())
                {
                    nums.pop();
                    nums.push(a[i]);
                }
            }
        }
        return nums.top();
    }
};

Submit result:

Insert picture description here

Method 4: Quick Sort

Fast sorting idea: divide the elements to be sorted into two independent parts through a sorting, and the elements of one part of the records are smaller than the elements of the other part of the records, and then the two parts of the records can be sorted separately until the entire sequence is ordered until. The specific approach is as follows:

  1. First select the base element base (first element, middle element, last element, random element, etc.).
  2. Take the benchmark element as the benchmark, put the elements smaller than the benchmark element in front, and put the elements larger than the benchmark element behind.
  3. Then it is divided into two groups of data based on the reference element.
  4. Repeat steps 1, 2 and 3 for the two groups of elements until the comparison and sorting are completed.

The worst running time of fast queue is O(n^2), and the average running time is O(nlogn). Due to the comparison of skip exchanges, it is unstable! The dynamic demonstration process is as follows:

Insert picture description here

The C++ implementation method of quick sort is as follows:

vector<int> quickSort(vector<int>&nums, int start, int end)
{
	if (start >= end) return nums;
	int base = nums[start];
	int i = start;
	int j = end;
	while (i < j)
	{
        while (i < j && nums[j] >= base) j--; //从右往左,寻找比base小的数
        swap(nums[i], nums[j]); //找到比base小的数,即与base交换位置
        while (i < j && nums[i] <= base) i++; //从左往右,寻找比base大的数
        swap(nums[i], nums[j]); //找到比base大的数,即与base交换位置
	}
	quickSort(nums, start, i - 1);
	quickSort(nums, i + 1, end);
	return nums;
}

For this question, you can first use the fast sorting method for global sorting, and then directly return to the Kth largest:

class Solution {
public:
    vector<int> quickSort(vector<int>&nums, int start, int end)
    {
        if (start >= end) return nums;
        int base = nums[start];
        int i = start;
        int j = end;
        while (i < j)
        {
            while (i < j && nums[j] >= base) j--; //从右往左,寻找比base小的数
            swap(nums[i], nums[j]); //找到比base小的数,即与base交换位置
            while (i < j && nums[i] <= base) i++; //从左往右,寻找比base大的数
            swap(nums[i], nums[j]); //找到比base大的数,即与base交换位置
        }
        quickSort(nums, start, i - 1);
        quickSort(nums, i + 1, end);
        return nums;
    }
    
    int findKth(vector<int> a, int n, int K) {
        quickSort(a, 0, n-1);
        return a[n-K];
    }
};

Obviously, this is not the best result. We further considered and found that in the fast sorting process, if the number of elements on the right of base exceeds K, then the result must be on the right of base, and the elements on the left can be sorted without consideration . Therefore, in the iterative process, we add a sentence of judgment, so that the time complexity of the calculation can be further reduced. As follows:

class Solution {
public:
    vector<int> quickSort(vector<int>&nums, int start, int end, int K)
    {
        if (start >= end) return nums;
        int base = nums[start];
        int i = start;
        int j = end;
        while (i < j)
        {
            while (i < j && nums[j] >= base) j--; //从右往左,寻找比base小的数
            swap(nums[i], nums[j]);
            while (i < j && nums[i] <= base) i++;
            swap(nums[i], nums[j]);
        }
        if(nums.size()-i<K) //如果base右边的数超过K个,则第K大数肯定在base右边,此时就不需要对base左边的进行排序
            quickSort(nums, start, i - 1, K);
        quickSort(nums, i + 1, end, K);
        return nums;
    }
    
    int findKth(vector<int> a, int n, int K) {
        quickSort(a, 0, n-1, K);
        return a[n-K];
    }
};

Final submission result:

Insert picture description here

Reference link: