学步园

首先说明一下快速排序是对冒泡排序的改进。为什么这么说呢？想一下冒泡排序，它把序列分成了两部分，前半部分无序，后半部分升序排列，并且后半部分的数都大于前半部的数。

由此可得到快速排序和冒泡排序的一些共同点：

1. 都要经历n趟排序
2. 每趟排序要经历O(n)次比较
3. 都是后半部分元素比前半部大

而不同之处就在于冒泡排序的交换操作发生相邻的元素之间，即一趟排序可以要经过多次交换操作；快速排序的交换操作发生在间隔比较远的两个元素之间，一趟排序要经过交换操作次数会少一些。

下面给出快速排序的递归和非递归实现代码：

?

#include<iostream>


#include<vector>


#include<stack>


#include<cstdlib>


#include<algorithm>


using
namespace std;

  

/**把数组分为两部分，轴pivot左边的部分都小于轴右边的部分**/

template
<typename
Comparable>

int
partition(vector<Comparable> &vec,int
low,int
high){

    Comparable pivot=vec[low]; 
//任选元素作为轴，这里选首元素

    while(low<high){


        while(low<high && vec[high]>=pivot)


            high--;


        vec[low]=vec[high];


        while(low<high && vec[low]<=pivot)


            low++;


        vec[high]=vec[low];


    }


    //此时low==high


    vec[low]=pivot;


    return
low;

}

  

/**使用递归快速排序**/

template<typename
Comparable>

void
quicksort1(vector<Comparable> &vec,int
low,int
high){

    if(low<high){


        int
mid=partition(vec,low,high);

        quicksort1(vec,low,mid-1);


        quicksort1(vec,mid+1,high);


    }


}

  

/**使用栈的非递归快速排序**/

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);


            }       


        }


    }


}

  

int
main(){

    int
len=1000000;

    vector<int> vec;


    for(int
i=0;i<len;i++)

        vec.push_back(rand()); 


    clock_t
t1=clock();


    quicksort1(vec,0,len-1);


    clock_t
t2=clock();


    cout<<"recurcive  "<<1.0*(t2-t1)/CLOCKS_PER_SEC<<endl;


      

    //重新打乱顺序


    random_shuffle(vec.begin(),vec.end());


          

    t1=clock();


    quicksort2(vec,0,len-1);


    t2=clock();


    cout<<"none recurcive  "<<1.0*(t2-t1)/CLOCKS_PER_SEC<<endl;


      

    return
0;

}

orisun@zcypc:~g++quicksort.cpp−oqsorisun@zcypc:  
./qs
recurcive 0.38
none recurcive 0.47

可以看到非递归的算法比递归实现还要慢。下面解释为什么会这样。

递归算法使用的栈由程序自动产生，栈中包含：函数调用时的参数和函数中的局部变量。如果局部变量很多或者函数内部又调用了其他函数，则栈会很大。每次递归调用都要操作很大的栈，效率自然会下降。

而对于非递归算法，每次循环使用自己预先创建的栈，因此不管程序复杂度如何，都不会影响程序效率。

对于上面的快速排序，由于局部变量只有一个mid，栈很小，所以效率并不比非递归实现的低。