【转】三种快速排序算法的实现（递归算法、非递归算法、三路划分快速排序）

原文：http://blog.csdn.net/left_la/article/details/8206405

快速排序的三个步骤：

1、分解：将数组A[l...r]划分成两个（可能空）子数组A[l...p-1]和A[p+1...r]，使得A[l...p-1]中的每个元素都小于等于A(p)，而且，小于等于A[p+1...r]中的元素。下标p也在这个划分过程中计算。

2、解决：通过递归调用快速排序，对数组A[l...p-1]和A[p+1...r]排序。

3、合并：因为两个子数组时就地排序，将它们的合并并不需要操作，整个数组A[l..r]已经排序。

1.快速排序的基础实现：

QUICKSORT(A, l, r)

if l < r

   then q = PARTION(A, l, r)

        QUICKSORT(A, l, p-1)

        QUICKSORT(A, p+1, r)

 

两路PARTION算法主要思想：

move from left to find an element that is not less

move from right to find an element that is not greater

stop if pointers have crossed

exchange

实现代码：

int partition(double* a, int left, int right)  
{  
    double x = a[right];  
    int i = left-1, j = right;  
    for (;;)  
    {  
        while(a[++i] < x) { }  
        while(a[--j] > x) { if(j==left) break;}  
        if(i < j)   
            swap(a[i], a[j]);  
        else break;  
    }  
    swap(a[i],a[right]);  
    return i;  
}  
  
void quickSort1(double* a, int left, int right)  
{  
    if (left<right)  
    {  
        int p = partition(a, left, right);  
  
        quickSort1(a, left, p-1);  
        quickSort1(a, p+1, right);  
    }  
}  

2.非递归算法：其实就是手动利用栈来存储每次分块快排的起始点，栈非空时循环获取中轴入栈。

实现代码：

void quickSort2(double* a, int left, int right)  
{  
    stack<int> t;  
    if(left<right)  
    {  
        int p = partition(a, left, right);  
  
        if (p-1>left)  
        {  
            t.push(left);  
            t.push(p-1);  
        }  
        if (p+1<right)  
        {  
            t.push(p+1);  
            t.push(right);  
        }  
  
        while(!t.empty())  
        {  
            int r = t.top();  
            t.pop();  
            int l = t.top();  
            t.pop();  
  
            p = partition(a, l, r);  
  
            if (p-1>l)  
            {  
                t.push(l);  
                t.push(p-1);  
            }  
            if (p+1<r)  
            {  
                t.push(p+1);  
                t.push(r);  
            }  
  
        }  
    }  
} 

3.三路划分快速排序算法：

实现代码：

void quickSort3Way(double a[], int left, int right)  
{  
    if(left < right)  
    {  
        double x = a[right];  
        int i = left-1, j = right, p = left-1, q = right;  
        for (;;)  
        {  
            while (a[++i] < x) {}  
            while (a[--j] > x) {if(j==left) break;}  
            if(i < j)  
            {  
                swap(a[i], a[j]);  
                if (a[i] == x) {p++; swap(a[p], a[i]);}  
                if (a[j] == x) {q--; swap(a[q], a[j]);}  
            }  
            else break;  
        }  
        swap(a[i], a[right]); j = i-1; i=i+1;  
        for (int k=left; k<=p; k++, j--) swap(a[k], a[j]);  
        for (int k=right-1; k>=q; k--, i++) swap(a[i], a[k]);  
  
        quickSort3Way(a, left, j);  
        quickSort3Way(a, i, right);  
    }  
}

4.测试代码：

#include <iostream>
#include <stack>
#include <ctime>
using namespace std;

// 产生（a,b）范围内的num个随机数
double* CreateRand(double a, double b, int num)
{
    double *c;
    c = new double[num];
    srand((unsigned int)time(NULL));
    for (int i=0; i<num; i++)
        c[i] = (b-a)*(double)rand()/RAND_MAX + a;
    return c;
}

// 两路划分，获取中轴，轴左边数小于轴，轴右边数大于轴
double partition(double* a, int left, int right)
{
    ...
}

// 1.递归快速排序，利用两路划分
void quickSort1(double* a, int left, int right)
{
    ...
}

// 2.非递归快速排序，手动利用栈来存储每次分块快排的起始点，栈非空时循环获取中轴入栈
void quickSort2(double* a, int left, int right)
{
    ...
}

// 3.利用三路划分实现递归快速排序
void quickSort3Way(double a[], int left, int right)
{
    ...
}

void main()
{
    double *a, *b, *c;
    int k=10000000;
    time_t start,end;

    a = CreateRand(0,1,k);
    b = CreateRand(0,1,k);
    c = CreateRand(0,1,k);

    start = clock();
    quickSort1(a,0,k-1);
    end = clock();
    cout<<"1.recursive "<<1.0*(end-start)/CLOCKS_PER_SEC<<" seconds"<<endl;

    start = clock();
    quickSort2(b,0,k-1);
    end = clock();
    cout<<"2.non-recursive "<<1.0*(end-start)/CLOCKS_PER_SEC<<" seconds"<<endl;

    start = clock();
    quickSort3Way(c,0,k-1);
    end = clock();
    cout<<"3.3 way "<<1.0*(end-start)/CLOCKS_PER_SEC<<" seconds"<<endl;

    cout<<endl;
    system("pause");
}

 

result:

1.recursive 1.951 seconds

2.non-recursive 2.224 seconds

3.3 way 1.677 seconds

结果可以看出非递归算法由于需要手动进行算法过程中的变量保存，执行效率低于递归算法；3路划分算法利用少量多余的交换减少了快排的复杂度，执行效率高于传统2路快排算法。