快速排序经典算法（分治法，挖坑法，前后指针法，非递归）

74 阅读 0 评论 49 点赞

我是靠谱客的博主纯情河马，最近开发中收集的这篇文章主要介绍快速排序经典算法（分治法，挖坑法，前后指针法，非递归），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

快速排序最优的情况就是当关键值位于序列中间时
快速排序最坏的情况就是对已序的序列进行排序
时间复杂度：O(N^2)最差
使用场景:数据量大而杂乱的序列，避免出现最坏的情况
快速排序递归算法之分治法
基本思路：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

//取一个关键元素，将序列分为两部分，然后分别排序
int partion(int arr[], int left, int right)
{
    int begin = left;
    int end = right-1;
    int key = arr[right];//关键元素

    while (begin < end)
    {
        //找到一个比关键元素大的元素
        while (begin<end&&arr[begin] <= key)
            begin++;
        //找到一个比关键元素晓得元素
        while (begin<end&&arr[end] >= key)
            end--;
        if (begin<end)
        {
            //交换
            std::swap(arr[begin], arr[end]);
            begin++;
            end--;

        }
    }
    if (begin != right&&arr[begin]>arr[right])
    {
        std::swap(arr[begin], arr[right]);
        return begin;
    }
    return right;

}
//递归算法
void QuickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int mid = partion(arr, left, right);
        QuickSort(arr, left, mid - 1);
        QuickSort(arr, mid + 1, right);
    }

}

快速排序递归算法之挖坑法
基本思路：
1、寻找pos位，然后将其分为两段数组，然后对这两段数组递归排序；
2、指定一个基数key（三数取中法），定义两个指针begin一个指向起始位置，end一个指向最后一个元素的位置。begin寻找比基数（key）大的数字，找到后将begin的数据赋给end，begin成为一个坑，然后end寻找比基数（key）小的数字，找到将end的数据赋给begin，end成为一个新坑，循环这个过程，直到begin指针与end指针相遇，然后将temp的数据返回给那个坑，然后进行递归操作。

int partion(int arr[], int left, int right)
{
    int begin = left;
    int end = right;
    int key = arr[right];
    while (begin < end)
    {
        while (begin<end&&arr[begin] <= key)
            begin++;
        if (begin<end)
            arr[right] = arr[begin];//begin成为新坑
        while (begin<end&&arr[end] >= key)
            end--;
        if (begin<end)
            arr[begin] = arr[end];//end成为新坑
    }

    arr[begin] = key;//用key填坑
    return begin;

}
void QuickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int mid = partion(arr, left, right);
        QuickSort(arr, left, mid - 1);
        QuickSort(arr, mid + 1, right);
    }

}

快速排序递归算法之前后指针法
基本思路：
定义两个指针，一前一后，前面指针找比基数小的数，后面指针找比基数大的数，前面的指针找到后，将前后指针所指向的数据交换，当前面的指针遍历完整个数组时，将基数值与后指针的后一个位置的数据进行交换，然后以后指针的后一个位置作为分界，然后将数组分开，进行递归排序。

int partion(int arr[], int left, int right)
{
    int pCur = left;//找大数
    int prev =pCur-1 ;//找小数
    int key = arr[right];
    while (pCur <= right)
    {
        if (arr[pCur] <= key&&++prev!=pCur)
        std::swap(arr[prev], arr[pCur]);
        pCur++;
    }
    return prev;
}
void QuickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int mid = partion(arr, left, right);
        QuickSort(arr, left, mid - 1);
        QuickSort(arr, mid + 1, right);
    }

}

快速排序算法之非递归
基本思路：利用栈保存左右区间
1、左右区间入栈（先右后左）
2、取栈顶元素，出栈
3、排序
4、入栈，先右后左

void QuickSort1(int arr[], int left, int right)
{
    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)
        {
            int div = partion(arr,left,right);
            s.push(right);
            s.push(div + 1);
            s.push(div - 1);
            s.push(left);
        }
    }
}

快速排序算法优化：
无论是分治法还是挖坑法首先都需要选取一个关键元素作为基数，但是如何选取才是最优算法呢？下面介绍三数取中法。
所谓三数取中法就是，在待排序序列的第一个元素，中间元素和最后一个元素中取大小位于中间的那个元素。

    //三数取中法
int GetKeyIdx(int arr[], int left, int right)
{
    int mid = right - ((right - left) >> 1);
    if (arr[left] < arr[right])
    {
        if (arr[mid] < arr[left])
            return left;
        else if (arr[mid]>arr[right])
                return right;
            else
                return mid;
    }
    else
    {
        if (arr[mid] < arr[right])
            return right;
        else if (arr[mid]>arr[left])
                return left;
            else
                return mid;
    }
}