#include<iostream>
#include<vector>
using namespace std;
//递归版本
void quickSort(int A[],int s,int t){
    if (s >= t){
        return;
    }
    int i = s;
    int j = t + 1;
    while (true){
        do{
            i++;
        } while (A[i] < A[s]&&i<t);
        do{
            j--;
        } while (A[j] > A[s]&&j>s);
        if (i < j){
            std::swap(A[i], A[j]);
        }
        else{
            std::swap(A[s], A[j]);
            break;
        }
    }
    quickSort(A, s, j-1);
    quickSort(A, j+1 , t);
}
//非递归版本
class node{
public:
    int start = 0;
    int end = 0;
    node(int _start,int _end){
        start = _start;
        end = _end;
    }
};
void quickSort(int A[],node node0){
    vector<node> STACK;
    int s = -1;
    int t = -1;
    STACK.push_back(node0);
    while (true){
        if (STACK.empty()){
            return;
        }
        else{
            node tmp = STACK.back();
            STACK.pop_back();
            s = tmp.start;
            t = tmp.end;
            if (s >= t){
                continue;
            }
        }
        int i = s;
        int j = t + 1;
        while (true){
            do{
                i++;
            } while (A[i]<A[s] && i < t);
            do{
                j--;
            } while (A[j] > A[s] && j>s);
            if (i < j){
                std::swap(A[i], A[j]);
            }
            else{
                std::swap(A[s], A[j]);
                break;
            }
        }
        STACK.push_back(node(s,j-1));
        STACK.push_back(node(j+1,t));
    }

}
int main(){
    int A[] = { -1, -2, -3, -4, -5 };
    quickSort(A, 0, 4);  //递归
    int B[] = { -1, -2, -3, -4, -5 };
    quickSort(B, node(0, 4));
    cout << "递归" << endl;
    for (int i = 0; i < 5; ++i){
        cout << A[i] << endl;
    }
    cout << "非递归" << endl;
    for (int i = 0; i < 5; ++i){
        cout << B[i] << endl;
    }
    system("pause");
}