你好,游客 登录 注册 发布搜索
背景:
阅读新闻

对于快速排序的理解

[日期:2016-11-25] 来源:CSDN博客  作者: [字体: ]

我们今天来研究下快速排序,快速排序的一个整体的思想就是分治的思想,在这个过程当中,首先对一个大区间进行单趟快速排序,然后把大区间分成多个区间,再去进行单趟排序,一直到这个区间中的元素只剩下一个元素,这样重复以后就可以得到最后的排序后的结果。

1.单趟排序分析 

快速排序的最重要的就是单趟排序,接下来就是进行分治的单趟排序,所以我们来重点说一下单趟排序。

我们在这里介绍关于快速排序的单趟排序的三种方法。

左右指针法: 这种方法我们首先需要选择一个key,然后给定一个left和一个right,维护left和right这段区间,在此期间,left要++,right要–,然后left找到比key大的一个数,right找到比key小的一个数,把他们进行交换,一直到left==right,这个时候级就可以把key放到位置上了。这就是最简单选key的方法的单趟排序,进行完单趟排序后,这个时候只把key值放到了该出现的位置,然后进行分割区间,转换为子问题递归。 

//左右指针法
template<typename T>
int portsort(T* arr, int begin, int end)
{
    assert(arr);
    int left = begin;
    int right = end;
    //利用三位取中优化效率,避免key是最小或者最大值的情况。
    int mid = SelectMid(arr, begin, end);
    std::swap(arr[mid], arr[end]);

    T key = arr[end];
    while (left<right)
    {
        while (left<right&&arr[left] <= key)
        {
            left++;
        }

        while (left<right&&arr[right] >= key)
        {
            right--;
        }
        //左边比key大的和右边比key小的进行交换
        if (arr[left]>arr[right])
        {
            swap(arr[left], arr[right]);
        }
    }
    //修正放入key
    swap(arr[left], arr[end]);

    return left;
}

挖坑法:首先找一个最左或者是最右端作为一个起始坑,保存坑中的值,然后如果在最左,那么就让left找一个比保存值大的,然后进行把这个值填坑,填完以后现在这个值的这个位置就变成了坑,然后我们继续让right在区间内找一个比保存值小的,找到以后填了刚才的坑,现在这个位置变成了新坑,这样一直继续下去,直到left==right,这个时候坑无法再次变动,把保存的初始值填入坑中。这个就是挖坑法的单趟排序。 

//挖坑法
template<typename T>
int PortSort2(T* arr, int begin, int end)
{
    assert(arr);
    int left = begin;
    int right = end;
    int mid = SelectMid(arr, begin, end);
    std::swap(arr[mid], arr[end]);
    //最后一个作为坑
    T hole = arr[end];
    while (left<right)
    {
        while (left<right&&arr[left] <= hole)
        {
            left++;
        }
        //填坑
        if (left < right)
            arr[right--] = arr[left];
        while (left < right&&arr[right] >= hole)
        {
            right--;
        }
        //填坑
        if (left < right)
            arr[left++] = arr[right];
    }
    //最后位置为坑初始元素
    arr[left] = hole;
    return left;
}

前后指针法:,一个cur,一个prev,这个时候prev初始化为begin-1, 

然后我们就是cur找一个比key小的,找到以后prev++,然后把arr[prev]和arr[end]进行交换

其实达到的效果就是把小的放到前面,放到前面。最后把key放到prev+1的位置就好了。

//第三种方法:前后指针方法,一个cur,一个prev,这个时候prev初始化为begin-1,
//然后我们就是cur找一个比key小的,找到以后prev++,然后把arr[prev]和arr[end]进行交换
//其实达到的效果就是把小的放到前面,放到前面。最后把key放到prev+1的位置就好了。

template<typename T>
int PortSort3(T* arr, int begin, int end)
{
    assert(arr);
    int prev = begin-1;
    int cur = begin;
    int pos = SelectMid(arr, begin, end);
    std::swap(arr[pos], arr[end]);
    T key = arr[end];
    while (cur < end)
    {
        if (arr[cur]<key&&++prev != cur)
        {
            std::swap(arr[cur], arr[prev]);
        }
        cur++;
    }
    std::swap(arr[++prev], arr[end]);
    return prev;
}

2.递归快排实现 

递归的实现很简单就是首先对整个区间进快排,然后分成两个小区间快排,最后再转化成递归问题进行快排。

template<typename T>
void QuickSort(T* arr, int begin, int end)
{
    assert(arr);
    if (begin<end)
    {
        //进行第一次单趟排序
        int div = PortSort(arr, begin, end);
        //递归子问题,划分区间
        QuickSort(arr, begin, div - 1);
        //递归子问题
        QuickSort(arr, div + 1, end);
    }

}

3.非递归快排的实现 

非递归的方式实现快速排序:

我们首先认识到,对于递归的问题转换成非递归,我们可以利用栈的数据特性来实现,在栈中保留下来递归的条件,这样就可以达到我们想要的效果了。

这里的条件就是我们来简单的控制begin和end就可以实现。

//非递归的快速排序
//非递归的解决方式就是利用栈进行解决
template<typename T>
void QuickSort4(T* arr, int begin, int end)
{
    assert(arr);
    std::stack<int> q;
    q.push(begin);
    q.push(end);
    while (!q.empty())
    {
        int right = q.top();
        q.pop();
        int left = q.top();
        q.pop();
        if (right > left)
        {
            int div = PortSort2(arr, left, right);

            q.push(left);
            q.push(div - 1);

            q.push(div + 1);
            q.push(right);
        }
    }
}

4.快速排序的优化思路 

对于快速排序有的优化思路:

三数取中法:为了防止出现我们所选取的可以是最大的或者最小的,造成一个快速排序的效率接近了冒泡排序的效率。为了更加高效,就需要使用三数取中的方法。

//快排的优化的方法:三位取中
//取得一个中位数,对于快排来说,可以使得时间复杂度更加接近logN
template<typename T>
int SelectMid(T* arr, int begin, int end)
{
    int left = begin;
    int right = end;

    //(begin+end)>>1;
    int mid = begin + ((end - begin) >> 1);

    if (arr[left]<arr[mid])
    {
        if (arr[right]>arr[mid])
            return mid;
        if (arr[left] < arr[right])
            return right;
        else
            return left;
    }
    else
    {
        if (arr[right] < arr[mid])
            return mid;
        if (arr[right]>arr[left])
            return left;
        else
            return right;
    }
}

可以优化递归的层数,对一些接近有序的情况使用插入排序。可以优化时间复杂度接近N。

所以我们可以修改代码:

template<typename T>
void QuickSort1(T* arr, int begin, int end)
{
    assert(arr);
    if (end-begin > 13)
    {
        int div = portsort(arr, begin, end);
        QuickSort1(arr, begin, div - 1);
        QuickSort1(arr, div + 1, end);
    }
    else
    {
        InsertSort(arr+begin, (end - begin + 1) );
    }

}

注:插入排序的实现详见我前面的博客。

5.总结 

快速排序在优化以后效率可以达到O(logN)。在同为O(N*logN)的几种排序方法中效率较高

 
收藏 推荐 打印 | 录入:admin | 阅读:
相关新闻      
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款