三路并排

[bosthhe1]

void ThreeRoadSort(int *a,int begin,int end)
{
    if (begin >= end)
        return;
    int key = a[begin];
    int left = begin;
    int cur = left +1 ;
    int right = end;
    while (right >= cur)
    {
        if (key > a[cur])
        {
            swap(a[cur], a[left]); cur++; left++;
        }
        else if (key < a[cur])
        {
            swap(a[cur], a[right]); right--;
        }
        else
        {
            cur++;
        }
    }
    ThreeRoadSort(a, begin, left - 1);
    ThreeRoadSort(a, right+1, end);
}