快速排序在实际应用中会面对大量具有重复元素的数组。举个例子，假如在排序过程中一个子数组已全部为重复元素，则对于此数组排序就应该停止了，但快排算法依然将其切分为更小的数组。这种情况下快排的性能尚可，但存在着巨大的改进潜力。（从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;
}
下面是《算法（第四版）》上对算法切分轨迹的一个示例说明：
对于包含大量重复元素的数组，这个算法将排序时间从线性对数级降到了线性级别。
