数据结构：快速排序非递归实现、优化及内省排序详解

前言

基于递归的方式学习了快速排序和归并排序，今天我们来深究快速排序，使用栈的数据结构非递归实现快排，优化快排（三路划分）。

一、非递归实现快排

上篇博客基于递归实现了三个版本的快排，hoare 版本，挖坑法，前后指针法。其实就是围绕基准值进行操作，不管哪一种版本，都离不开找基准值，递归得到子区间。快排的非递归版本也离不开找基准值，但是对区间进行了处理，使用到栈的数据结构。

把一个大区间分成几个小区间。

给定初始数据样例，我们正常使用前后指针的方法进行快排，找基准值。

基准值，以及区间的下标。

我们把 0-2 的区间左右下标入栈，4-5 的区间下标入栈，相当于递归到子区间的操作。栈是遵循先进后出的规则，刚好和递归的区间的遍历顺序一样。每次前后指针找完基准值，就把分出来的左右区间下标入栈。但还是要注意越界的情况，比如基准值的节点在最左边或者最右边。

假设基准值的下标为 keyi，那么右区间就是 [keyi+1，end],左区间就是 [begin，keyi-1]。

上图的有些区间就是不符合条件的。

基本思路都叙述的差不多了，上代码。

void QuickSortNonR(int* a, int left, int right) {
    std::stack<int> st; // 定义一个栈
    st.push(right); // 这里先让右端下标入栈 因为栈是先进后出的
    st.push(left); // 再让左端下标入栈
    while (!st.empty()) {
        int begin = st.top(); // 取当前栈顶元素，也就是区间的左端
        st.pop();
        int end = st.top(); // 取右端元素
        st.pop();
        int prev = begin, cur = prev + 1; // 然后就是前后指针找基准值
        int keyi = begin;
        while (cur <= end) {
            if (a[cur] < a[keyi] && ++prev != cur) {
                swap(a[prev], a[cur]);
            }
            ++cur;
        }
        swap(a[keyi], a[prev]);
        keyi = prev; // 这里找到了基准值
        if (keyi + 1 < end) 
        {
            st.(end);
            st.(keyi + ); 
        }
         (keyi -  > begin) {
            st.(keyi - );
            st.(begin); 
        }
    }
}