欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序的相关算法--快排1【菜鸟学习日记】

程序员文章站 2022-04-15 20:37:59
...

今天来总结一下排序算法中的快排算法

快排其实就是对冒泡排序的一种改进。
快排 快排,就是字面的意思排序很快,一会儿来研究一下

基本思想:

它的基本思想就是,通过一趟排序,找到关键字key的正确位置,并将待排序列分为两个独立的部分,一部分比key小,另一部分比key大,也就是一部分整体比另一部分小,然后再对这两部分分别排序。

就如下图,经过一趟排序后,将5放到了正确的位置,并将数组分为两个部分,左边部分比5小,右边部分比5大,左边整体小于右边
排序的相关算法--快排1【菜鸟学习日记】
排序的相关算法--快排1【菜鸟学习日记】

快排之“分治” ——分而治之

从上面的实现过程我们可以看出,快排也是“分治”算法的实现
关于分治的思想与并归一样,可以查看归并排序

快排效率分析

  • 时间复杂度:快排的时间复杂度为NlgN,但若起初序列的排序有序或基本有序,那么快排就成了冒泡排序,时间复杂度就是O(n*n)了。
  • 空间复杂度:再来分析空间复杂度,快排需要一个栈空间来实现递归。若每一趟都将待排序列均匀的分割成长度接近相等的两部分(就有点像满二叉树一样),那么栈的最大深度为lgN(树的深度),但若每趟排序,总是一边大于一边很多(序列本身有序或基本有序),则为最坏情况,栈的最大深度为n。具体的分析,以及改进的方法具体的改进方法

以下三种方法是每一趟快排比较的实现方法,都是经过一趟排序将key关键字找到并放到正确的位置,并将序列分为以key为界的两部分,并且一部分比另一部分小

1、左右指针法

定义两个指针,一个从前向后找比key大的,一个从后向前找比key小的,找到后进行交换,就将小的交换到了前面,大的交换到了后面,当left和right相遇时,就找到了key的正确位置
注意点:当两个指针相遇时,有一种特殊情况不用交换,就是如果key本身就在对的位置
排序的相关算法--快排1【菜鸟学习日记】
排序的相关算法--快排1【菜鸟学习日记】

//左右指针法
int _PartSort1(int* a, int begin, int end)
{
    assert(a);
    int key = end;
    --end;

    while (begin<end)
    {
        while (begin<end&&a[begin] <a[key])
        {
            ++begin;
        }
        while (begin<end&&a[end]>a[key])
        {
            --end;
        }
        //left找到比key小的,right找到比key大的,交换
        swap(a[begin], a[end]);
    }
    //begin=end
    if (a[begin]>a[key])
    {
        swap(a[begin], a[key]);
        return begin;
    }
    return key;
}

2、挖坑法
排序的相关算法--快排1【菜鸟学习日记】

//挖坑法
int _PartSort2(int* a, int begin, int end)
{
    int key = a[end];
    while (begin < end)
    {
        //比key小
        while (begin<end&&a[begin]<key)
        {
            ++begin;
        }
        a[end] = a[begin];
        while (begin<end&&a[end]>key)
        {
            --end;
        }
        a[begin] = a[end];
    }
    //将key放置回去
    a[begin] = key;
    return begin;
}

3、前后指针法(三种里最优的)
排序的相关算法--快排1【菜鸟学习日记】

//前后指针法
int _PartSort3(int* a, int begin, int end)
{
    int cur = begin;
    int prev = cur - 1;

    while (cur < end)
    {
        if (a[cur] < a[end] && ++prev != cur)
        {
            swap(a[prev], a[cur]);
        }
        ++cur;
    }
    swap(a[++prev], a[end]);
    return prev;
}

以上就是对与快排的三种方法的基本实现,还有一些问题可以进行优化,后面再优化!

相关标签: 快排