快排

[bosthhe1]

//三数取中
int Random(int* a, int left, int right)
{
    int mid = left + (right - left) / 2;
    if (a[mid] > a[left])
    {
        if (a[mid] < a[right])
            return right;
        if (a[left]>a[right])
            return left;
        return right;
    }
    //a[mid] < a[left]
    else
    {
        if (a[mid] > a[right])
            return mid;
        if (a[right] < a[left])
            return right;
        return left;
    }
}

[bosthhe1]

//快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    Swap(a[left],a[Random(a, left,right)]);
    int key = left;
    int end = right;
    int begin = left;
    while (end>begin)
    {
        while (end>begin&&a[end] >= a[key])
        {
            end--;
        }
        while (begin < end&&a[begin] <= a[key])
        {
            begin++;
        }
        Swap(a[end], a[begin]);
    }
    Swap(a[key], a[end]);
    key = end;
    return key;
}

[bosthhe1]

int PartSort2(int* a, int left, int right)
{
    int prev = left;
    int cur = prev+1;
    int key = left;
    while (cur <= right)
    {
        if (a[cur] < a[key])
        {
            Swap(a[++prev] , a[cur]);
        }
        cur++;
    }
    Swap(a[prev], a[key]);
    PartSort2(a, left, prev-1);
        PartSort2(a, prev+1, end);
}

[bosthhe1]

// 快速排序挖坑法
int PartSort3(int* a, int left, int right)
{
    Swap(a[left], a[Random(a, left, right)]);
    int hole = left;
    int tmp = a[hole];
    int begin = left; int end = right;
    while (end>begin)
    {
        while (end>begin&&a[end] >= tmp)
        {
            end--;
        }
        a[hole] = a[end];
        hole = end;
        while (end>begin&&a[begin] <= tmp)
        {
            begin++;
        }
        a[hole] = a[begin];
        hole = begin;
    }
    a[hole] = tmp;
    return hole;
}

[bosthhe1]

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
    Stack *ps = (Stack *)malloc(sizeof(Stack));
    StackInit(ps);
    StackPush(ps, right);
    StackPush(ps, left);
    int key = 0;
    while (!StackEmpty(ps))
    {
        int begin = StackTop(ps); StackPop(ps);
        int end = StackTop(ps); StackPop(ps);
        key = PartSort3(a, begin,end);
        if (begin < key - 1)
        {
            StackPush(ps, key - 1);
            StackPush(ps, begin);
        }
        if (end > key +1)
        {
            StackPush(ps, end);
            StackPush(ps, key + 1);
        }
    }
    StackDestroy(ps);
}