快排的非递归版本

quicksort_non_recursive.cpp

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



void quick_sort(vector<int> &v, int low, int high)
{
    stack<int> s;
    
    if(low<high)
    {
        int pivot = partition(v, low, high);
        if(low < pivot-1){
            s.push(low);
            s.push(mid-1);
        }
        if(mid+1 < high){
            s.push(mid+1);
            s.push(high);
        }
        int q, p;
        while(!s.empty()){
            q = s.top();
            s.pop();
            p = s.top();
            s.pop();
            int mid = partition(v, p, q);
            if(p< mid-1){
                s.push(p);
                s.push(mid-1);
            }
            if(mid+1<q){
                s.push(mid+1);
                s.push(q);       
            }
        }   
    }      
}