数据结构之快速排序

一、快速排序

    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快排中心思想代码演示：

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 if(right - left <= 1)
 return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);
 
 // 递归排[div+1, right)
 QuickSort(array, div+1, right);
}

代码实现：

// 三数取中
int GetMidi(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    // left mid right
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])  // mid是最大值
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else // a[left] > a[mid]
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] < a[right]) // mid是最小
        {
            return left;
        }
        else
        {
            return right;
        }
    }
}

//hoare
int PartSort1(int* a, int left, int right)
{
    int midi = GetMidi(a, left, right);
    Swap(&a[left], &a[midi]);

    int keyi = left;
    while (left < right)
    {
        // 找小
        while (left < right && a[right] >= a[keyi])
        {
            --right;
        }

        // 找大
        while (left < right && a[left] <= a[keyi])
        {
            ++left;
        }

        Swap(&a[left], &a[right]);
    }

    Swap(&a[keyi], &a[left]);
    return left;
};

代码实现：

int PartSort2(int* a, int left, int right)
{
    int midi = GetMidi(a, left, right);
    Swap(&a[left], &a[midi]);

    int key = a[left];
    // 保存key值以后，左边形成第一个坑
    int hole = left;

    while (left < right)
    {
        // 右边先走，找小，填到左边的坑，右边形成新的坑位
        while (left < right && a[right] >= key)
        {
            --right;
        }
        a[hole] = a[right];
        hole = right;

        // 左边再走，找大，填到右边的坑，左边形成新的坑位
        while (left < right && a[left] <= key)
        {
            ++left;
        }
        a[hole] = a[left];
        hole = left;
    }

    a[hole] = key;
    return hole;
}

代码实现：

int PartSort3(int* a, int left, int right)
{
    int midi = GetMidi(a, left, right);
    Swap(&a[left], &a[midi]);

    int prev = left;
    int cur = prev + 1;

    int keyi = left;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[prev], &a[cur]);
        }

        ++cur;
    }

    Swap(&a[prev], &a[keyi]);
    return prev;
}

快速排序递归代码：

void QuickSort(int* a, int begin, int end)
{
    if (begin >= end)
        return;

    int keyi = PartSort3(a, begin, end);//此处调用前后指针快排，也可调用其他两种排序方法
    // [begin, keyi-1] keyi [keyi+1, end]
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi+1, end);
}