三向切分的快速排序

快速排序在实际应用中会面对大量具有重复元素的数组。举个例子，假如在排序过程中一个子数组已全部为重复元素，则对于此数组排序就应该停止了，但快排算法依然将其切分为更小的数组。这种情况下快排的性能尚可，但存在着巨大的改进潜力。（从O(nlgn)提升到O(n)）

一个简单的改进想法就是将数组分为三部分：小于当前切分元素的部分，等于当前切分元素的部分，大于当前切分元素的部分。

E.W.Dijlstra（对，就是Dijkstra最短路径算法的发明者）曾经提出一个与之相关的荷兰国旗问题（一个数组中有分别代表红白蓝三个颜色的三个主键值，将三个主键值排序，就得到了荷兰国旗的颜色排列）。

他提出的算法是： 对于每次切分：从数组的左边到右边遍历一次，维护三个指针lt,gthe i，其中

• lt指针使得元素（arr[0]-arr[lt-1]）的值均小于切分元素；
• gt指针使得元素（arr[gt+1]-arr[N-1]）的值均大于切分元素；
• i指针使得元素（arr[lt]-arr[i-1]）的值均等于切分元素，（arr[i]-arr[gt]）的元素还没被扫描，切分算法执行到i>gt为止。

每次切分之后，位于gt指针和lt指针之间的元素的位置都已经被排定，不需要再去移动了。之后将（lo,lt-1）,（gt+1,hi）分别作为处理左子数组和右子数组的递归函数的参数传入，递归结束，整个算法也就结束。
三向切分的示意图：

代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
#define maxn 10000
int a[maxn];

void exchange( int i,int j )
{
    int tmp=a[i];
    a[i]=a[j];
    a[j]=tmp;
}

void qsort3way ( int lo,int hi )
{
    if( lo>=hi ) return;  //单个元素或者没有元素的情况
    int lt=lo;
    int i=lo+1;  //第一个元素是切分元素，所以指针i可以从lo+1开始
    int gt=hi;
    int v=a[lo];
    while( i<=gt )
    {
        if( a[i]<v )  //小于切分元素的放在lt左边，因此指针lt和指针i整体右移
            exchange( lt++,i++ );  
        else if ( a[i]>v )  //大于切分元素的放在gt右边，因此指针gt需要左移
            exchange( i,gt-- );
        else
            i++;
    }
    //lt-gt的元素已经排定，只需对it左边和gt右边的元素进行递归求解
    qsort3way( lo,lt-1 );    
    qsort3way( gt+1,hi );
}

int main()
{
    int n;
    cin>>n;
    for( int i=0; i<n; i++  )
        cin>>a[i];
    qsort3way( 0,n-1 );
    for( int i=0; i<n; i++  )
        cout<<a[i];
    cout<<endl;
    return 0;
}

下面是《算法（第四版）》上对算法切分轨迹的一个示例说明：

对于包含大量重复元素的数组，这个算法将排序时间从线性对数级降到了线性级别。