c++ 快速选择排序-递归和非递归实现

#史上最好记的快速排序

class Solution {
public:
    // 循环不不定式
    // [low, clapboard] 小于等于piovt的部分
    // [clapboard + 1, i) 已处理且大于piovt的部分
    // [i, high] 待处理部分
    int partition(vector<int> &nums, int low, int high, function<bool(const int, const int)> cmp) {
        int piovt = nums[high];
        int clapboard = low - 1;
        for (int i = low; i < high; i++) {
            if (cmp(nums[i], piovt)) {
                swap(nums[++clapboard], nums[i]);
            }
        }
        swap(nums[++clapboard], nums[high]);
        return clapboard;
    }
	
	// 基于递归的实现
    void quickSort(vector<int> &nums, int low, int high, function<bool(const int, const int)> cmp = less_equal<>{}) {
        if (low >= high) {
            return;
        }
        int q = partition(nums, low, high, cmp);
        quickSort(nums, low, q - 1, cmp);
        quickSort(nums, q + 1, high, cmp);
    }

    struct Item {
        int low, high;
    };
	
	// 基于栈的实现
    void quickSort_stack(vector<int> &nums, int low, int high, function<bool(const int, const int)> cmp = less_equal<>{}) {
        if (low >= high) {
            return;
        }
        stack<Item> st;
        st.push({low, high});
        while (!st.empty()) {
            auto node = st.top();
            st.pop();
            int l = node.low;
            int h = node.high;
            if (l >= h) {
                continue;
            }
            int q = partition(nums, l, h, cmp);
            st.push({l, q - 1});
            st.push({q + 1, h});
        }
        return;
    }

    void sortIntegers(vector<int> &a) {
        // write your code here
        quickSort_stack(a, 0, (int)a.size() - 1, less_equal<>{});
    }
};