姓名：毛浩 学号：17029250003

【嵌牛导读】快速排序使用。

【嵌牛鼻子】算法

【嵌牛提问】快速排序的理解

【嵌牛正文】

快速排序和partition

@(基础算法)[快速排序|partition]

---

[TOC]

实例1

leetcode215

1.png

方法1

直接使用sort函数，返回n-k个
Time: O(nlogn)
Place: O(1)

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()-k];
    }
};

方法二

使用小顶堆
Time: O(nlogk)
Place: O(k)

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<int, vector<int>, greater<int> > q;
        for(int i=0; i<nums.size(); i++){
            if(i < k)   q.push(nums[i]);
            else{
                if(nums[i] > q.top()){
                    q.pop();
                    q.push(nums[i]);
                }
            }
        }
        return q.top();
    }
};

方法三

借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素

3.png
因此要找到最终位置为len-k的数，我们可以根据pivot的位置确定下一次partition的范围，即减而治之的思想

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int target = n - k;
        int left = 0, right = n - 1;
        while(1){
            int idx = partition(nums, left, right);
            if(idx == target)   return nums[idx];
            else if(idx < target)   left = idx + 1;
            else    right = idx - 1;
        }
        return nums[0];
    }
    int partition(vector<int>& nums, int left, int right){
        if(right == left)   return left;
        int num = rand() % (right - left) + left;//加个随机防止极端情况
        swap(nums[num], nums[left]);
        int pivot = nums[left];
        int idx = left;
        for(int i=left+1; i<=right; i++){
            if(nums[i] < pivot){
                idx++;
                swap(nums[idx], nums[i]);
            }
        }
        swap(nums[left], nums[idx]);
        return idx;
    }
};

实例2

leetcode75
我们在学习 快速排序 的时候知道，可以选择一个标定元素（称为 pivot ，一般而言随机选择），然后通过一次扫描，把数组分成三个部分：

4.png
第 2 部分元素就是排好序以后它们应该在的位置，接下来只需要递归处理第 1 部分和第 3 部分的元素。

经过一次扫描把整个数组分成 33 个部分，正好符合当前问题的场景。写对这道题的方法是：把循环不变量的定义作为注释写出来，然后再编码。

5.png
6.png

代码：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int size = nums.size();
        if(size < 2)    return;
        //[0, zero)->0
        //[zero, i)->1
        //[two, len-1]->2
        int i, zero, two;
        i = 0, zero = 0, two = size - 1;
        while(i <= two){
            if(nums[i] == 0){
                swap(nums[i], nums[zero]);
                zero++;
                i++;
            }
            else if(nums[i] == 1){
                i++;
            }
            else{
                swap(nums[i], nums[two]);
                two--;
            }
        }
    }
};