【数据结构】排序算法——快速排序

  快速排排序是效率非常高的排序算法之一。
  它的基本思想是:首先选择一个基准值,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都小于基准值,另一部分所有数据都大于基准值,并且经过一趟排序,所选择基准值已经换到了在它应该在的正确位置。然后再通过此方法堆这两部分数据分别进行快速排序,整个排序过程可以递归实现。但是具体的将待排序的数据分为两个部分的方法,却有很多:
  
举一个例子:

数组下标 0 1 2 3 4 5 6 7 8 9
待排序数据 7 1 4 8 2 0 9 6 3 5

我们取最后一个元素5为基准值key
第一种方法:

  1. 定义两个指针,begin和end分别指向第一个元素和最后一个元素,基准值key=arr[end];
  2. begin从前向后移动,当遇到大于key的时候停下来,end从后向前移动,当遇到小于key的时候停下,交换begin和end对应的元素;
  3. 重复上一步,直至begin与end相遇,begin对应的元素与key值进行交换。
    这里写图片描述
    此方法的实现代码如下:
size_t Pation1(int *arr, int left, int right)
{
    size_t begin = left;
    size_t end = right - 1;
    int key = arr[end];

    while (begin < end)
    {
        while (begin < end && arr[begin] <= key)
            begin++;
        while (begin < end && arr[end] >= key)
            end--;
        if (begin < end)
            swap(arr[begin], arr[end]);
    }
    if (begin != right-1)// 1 2 4 5 6
        swap(arr[begin], arr[right-1]);
    return begin;
}
void QuickSort(int *arr, int left, int right)
{ 
    if (left < right)
    {
        size_t div = Pation1(arr, left, right);
        QuickSort(arr, left, div);
        QuickSort(arr, div + 1, right);
    }
}

第二种方法:挖坑法

  1. 定义两个指针,begin和end分别指向第一个元素和最后一个元素,基准值key=arr[end];
  2. begin从前向后移动,当遇到大于key的时候停下来,将begin位置的数据放置end处,begin变为坑;
  3. end从后开始向前移动,当遇到小于key的时候停下来,将end处的数据放置坑(begin)处,end变为坑,begin开始移动;
  4. 重复2、3两步,直至begin与end相遇,最后的一个坑放key。
    这里写图片描述

此方法的实现代码如下:

size_t Pation2(int *arr, size_t left, size_t right)
{
    size_t begin = left;
    size_t end = right - 1;
    int key = arr[end];

    while (begin < end)
    {
        while (begin < end && arr[begin] <= key)
            begin++;
        if (begin < end)
            arr[end--] = arr[begin];
        while (begin < end && arr[end] >= key)
            end--;
        if (begin < end)
            arr[begin++] = arr[end];
    }
    if (begin != right-1)
        arr[begin] = key;//1 2 3 4 5 6
    return begin;
}
void QuickSort(int *arr, int left, int right)
{ 
    if (left < right)
    {
        size_t div = Pation2(arr, left, right);
        QuickSort(arr, left, div);
        QuickSort(arr, div + 1, right);
    }
}

第三种方法:追赶法

  1. 定义两个指针,cur和pre分别指向第一个元素和-1,基准值key=arr[end];
  2. cur从前向后移动,当遇到大于key的时候,cur++;当遇到小于key的时候,++pre后,如果pre与cur不在同一位置,则交换两个数据;
  3. 重复第2步,直至cur不小于right边界,再++pre,如果pre不与right在同一个位置,那么交换两个数据。

如下图所示:
这里写图片描述
这里写图片描述
此方法的实现代码如下:

size_t Pation3(int *arr, size_t left, size_t right)
{
    int index = GetMid(arr, left, right);
    if (index != right - 1)
        swap(arr[index], arr[right - 1]);
    int key = arr[right - 1];

    int cur = left;
    int pre = cur - 1;
    while (cur < right)
    {
        if (arr[cur] < key && ++pre != cur)
            swap(arr[pre], arr[cur]);
        cur++;
    }
    if (++pre != right)
        swap(arr[pre], arr[right-1]);
    return pre;
}
void QuickSort(int *arr, int left, int right)
{ 
    if (left < right)
    {
        size_t div = Pation3(arr, left, right);
        QuickSort(arr, left, div);
        QuickSort(arr, div + 1, right);
    }
}

以上实现的快速排序是递归的,递归也是可以转换成循环,我们利用循环+栈来实现,非递归的快排。

#include <stack>
void QuickSort(int *arr, size_t size)
{
    int left = 0;
    int right = size;
    stack<int> s;
    s.push(right);
    s.push(left);
    while (!s.empty())
    {
        left = s.top();
        s.pop();
        right = s.top();
        s.pop();

        if (left < right)
        {
            size_t div = Pation3(arr, left, right);
            s.push(div);//保存基准值左边数据的边界
            s.push(left);

            s.push(right);//保存基准值右边的数据的边界
            s.push(div + 1);
        }
    }
}

优化

  快速排序时间复杂度一般为O(N*logN),最坏为O(N*N),快速排序的性能取决于递归树的深度,在最优的情况下,递归树深度为logN,最坏的情况下,递归深度为N。所以,基准值key的选择至关重要,如果选择的不合适,那么递归深度将会变大,从而造成效率下降。
  对此,我们的解决方法是:三数取中法,顾名思义,就是在待排序数组中的首元素、中间元素、最后一个元素,这三个数据中选择中间大小的数据。
  
代码如下:

size_t GetMid(int *arr, size_t left, size_t right)
{
    size_t mid = left + ((right - left) >> 1);
    if (arr[left] < arr[right-1])
    {
        if (arr[left] > arr[mid])
            return left;
        else if (arr[right - 1] < arr[mid])
            return right - 1;
        else
            return mid;
    }
    else
    {
        if (arr[left] < arr[mid])
            return left;
        else if (arr[right - 1] > arr[mid])
            return right - 1;
        else
            return mid;
    }
}
相关文章
相关标签/搜索