快速排序三指针分区法

千公子

有相同元素值的快速排序——三分法
三分法有三个指针，一个向右扫描比主元小的元素指针，
一个记录与主元相等元素的指指，另一个是从右向左扫描
比主元大的元素指针。
将数组分为四个区，小于主元区，等于主元区，未知区，
与大于主元区

千公子

#include <iostream>

using namespace std;

void swap(int arr[], int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void quick_sort(int arr[], int left, int right)
{
    if(left >= right)
        return;

    int e = left + 1; //记录等于主元的指针
    int sp = left + 1; //扫描小于主元元素指针
    int bigger = right; //扫描大于主元元素指针
    int pivot = arr[left]; //主元
    while(sp <= bigger)
    {
        while(sp <= bigger && arr[sp] < pivot)
        {
            e++;
            sp++;
        }
        while(sp <= bigger && arr[sp] == pivot)
        {
            swap(arr, e, sp);
            e++;
            sp++;
        }
        while(sp <= bigger && arr[bigger] > pivot) 
            bigger--;
        
        if(sp < bigger)
            swap(arr, bigger, sp);
    }
    swap(arr, bigger, left);
    quick_sort(arr, left, bigger-1);
    quick_sort(arr, bigger+1, right);
}

int main()
{
    int arr[10] = {5, 1, 2, 4, 3, 6, 1, 1, 2, 2};
    quick_sort(arr, 0, 9);
    for(int i = 0; i<10; i++)
        cout << arr[i] << "\t";
    return 0;
}