快速排序【模板】

一、递归版本

手打递归版本

void quickSort(int *arr, int left,int right) {

    if(left>=right)
        return;

    int i=left,j=right;
    int standard = arr[left];

    while(i<j) {

        //find some elements bigger than standard
        while( i<j && arr[i] < standard)
            ++i;

        //find some elements smaller than standard
        while( i<j && arr[j] > standard)
            --j;

        //exchange arr.i and arr.j
        swap(arr[i],arr[j]);
    }
    // i == j where the standard should be

    quickSort(a,left,i-1);
    quickSort(a,i+1,right);
}

《数据结构理论与实践》版本：

int Partition(int *arr, int i,int j) {

    arr[0] = arr[i]; //arr[0] is a temp space

    while(i<j) {

        while(i<j && arr[j] >= arr[0]) --j;

        if( i < j) { //move the smaller element to the front
            arr[i] = arr[j];
            ++i;
        }

        while(i<j && arr[i] < arr[0]) ++i;

        if( i < j) { //move the bigger element to the tail
            arr[j] = arr[i];
            --j;
        }
    }

    arr[i] = arr[0];
    return i;
}

void quickSort(int *arr, int left,int right) {

    int i;
    if(left<right) {
        i = Partition(arr,left,right); //divide the arr into 2 parts
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
}

上面的版本都会有TLE
递归改进版（poj 2623 AC）：

void quickSort(int *arr, int left, int right){
    int i = left, j = right;
    int mid = arr[(i+j)/2];
    while(i <= j){
        while(arr[i] < mid) i ++;
        while(arr[j] > mid) j --;
        if(i <= j){
            int tmp;
            tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            i ++; j --;
        }
    }
    if(i < right) quickSort(arr,i, right);
    if(left < j) quickSort(arr,left, j);
}

二、非递归版本

/**使用栈的非递归快速排序**/
template<typename Comparable>
void quicksort2(vector<Comparable>
 &vec,int low,int high){
    stack<int>
 st;
    if(low<high){
        int mid=partition(vec,low,high);
        if(low<mid-1){
            st.push(low);
            st.push(mid-1);
        }
        if(mid+1<high){
            st.push(mid+1);
            st.push(high);
        }
        //其实就是用栈保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，对这段子序列进行partition操作
        while(!st.empty()){
            int q=st.top();
            st.pop();
            int p=st.top();
            st.pop();
            mid=partition(vec,p,q);
            if(p<mid-1){
                st.push(p);
                st.push(mid-1);
            }
            if(mid+1<q){
                st.push(mid+1);
                st.push(q);
            }      
        }
    }
}