Simple & Naive

三路快速排序是快速排序针对相等元素较多情况的改进版本。

三路快排的C实现：

void quicksort3(int *n, int len)
{
    int i=0, j=0, k=len-1;

    if (len<2) return;

    while (i<k) {
        if (*(n+i) < *(n+len-1)) {
            swap(n+ i++, n+ j++);
        } else if (*(n+i) == *(n+len-1)) {
            swap(n+i, n+ --k);
        } else {
            i++;
        }
    }

    // k-j is length of nums larger than tail num, len-k is length of nums
    // equal to tail num
    int m = (k-j) < (len-k) ? (k-j) : (len-k);
    int _i;
    for (_i=0; _i<m; _i++) {
        swap(n+j+_i, n+len-m+_i);
    }

    // j is len of nums less than tail num
    if (j>1) quicksort3(n, j);
    if (k-j>1) quicksort3(n+len-k+j, k-j);
}

三路快排比传统快排稍微复杂，但它继承了快排的所有优点，而且针对相等元素较多的情况速度提升非常明显。