int get_pivot_pos(int left, int right, vector<int> &nums) {
    int pivot = nums[left];
    while (left < right) {
        while (left < right && nums[right] >= pivot)
            right--;
        nums[left] = nums[right];
        while (left < right && nums[left] <= pivot)
            left++;
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

//递归
void quick_sort(int left, int right, vector<int> &nums) {
    if (left < right) {
        int pivot = get_pivot_pos(left, right, nums);
        quick_sort(left, pivot - 1, nums);
        quick_sort(pivot + 1, right, nums);
    }
}

//非递归
void quick_sort_no_recursion(int left, int right, vector<int> &nums) {
    if (left >= right)
        return;
    stack<int> s;
    s.push(left);
    s.push(right);
    while (!s.empty()) {
        int right = s.top();
        s.pop();
        int left = s.top();
        s.pop();
        int pivot = get_pivot_pos(left, right, nums);
        if (pivot - 1 > left) {//保存左边
            s.push(left);
            s.push(pivot - 1);
        }
        if (pivot + 1 < right) {//保存右边
            s.push(pivot + 1);
            s.push(right);
        }
    }
}

1.TOPK

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

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

package gongel_first;

import java.util.PriorityQueue;

public class Twohundred_fifteen {
    /**
     * 快排、快速排序
     */
    public int paritition(int[] nums, int low, int high) {
        int pivot = nums[low];
        while (low < high) {//下面顺序不能交换， 因为pivot首先保存的是low
            while (low < high && nums[high] >= pivot)
                high--;
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot)
                low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length)
            return -1;
        k = nums.length - k;//如果不进行此操作，则是找到数组中第k小的元素;例如4/5/6/7/8,第四大元素对应的下标为5-4=1
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int pivoit_pos = paritition(nums, low, high);
            if (pivoit_pos == k)
                return nums[pivoit_pos];
            else if (pivoit_pos > k)
                high = pivoit_pos - 1;
            else
                low = pivoit_pos + 1;
        }
        return nums[k];
    }

    /**
     * 优先队列实现小根堆
     */
    public int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int val : nums) {
            pq.add(val);
            if (pq.size() > k)//相当于nums.length-k；从nums中丢弃前nums.length-(k+1)+1=nums.length-k个最小的元素
                pq.poll();
        }
        return pq.peek();
    }
}

class Solution {
public:
    int findKthLargest(vector<int> &nums, int k) {
        if (nums.size() == 0)
            return -1;
        priority_queue<int, vector<int>, greater<int> > pq;
        for (auto num:nums) {
            pq.push(num);
            if (pq.size() > k)
                pq.pop();
        }
        return pq.top();
    }

    int findKthLargest2(vector<int> &nums, int k) {
        if (nums.size() == 0)
            return -1;
        k = nums.size() - k;
        int low = 0;
        int high = nums.size() - 1;
        while (low < high) {
            int pivot = paritition(low, high, nums);
            if (pivot == k)
                return nums[k];
            else if (pivot > k)
                high = pivot - 1;
            else
                low = pivot + 1;
        }
        return nums[k];
    }

    int paritition(int low, int high, vector<int> &nums) {
        int pivot = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= pivot)
                high--;
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot)
                low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }
};

2.三路快排

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

public class Seventy_five {
    /**
     * 三路快排
     */
    public void sortColors(int[] nums) {
        int zero = -1, one = 0, two = nums.length;
        while (one < two) {
            if (nums[one] == 0) {
                swap(nums, ++zero, one++);
            } else if (nums[one] == 2) {
                swap(nums, --two, one);
            } else {
                ++one;
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
public:
    void sortColors(vector<int> &nums) {
        int zero = -1;
        int one = 0;/指向不确定的颜色
        int two = nums.size();
        while (one < two) {
            if (nums[one] == 0) {
                swap(nums,++zero, one++);//左边已经扫过了，所以one++
            } else if(nums[one]==2){
                swap(nums,--two,one);//右边没有扫过，所以one暂停等着下一步来扫
            } else{
                one++;
            }
        }
    }

    void swap(vector<int> &nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

return the last