快速排序QuickSort

这篇具有很好参考价值的文章主要介绍了快速排序QuickSort。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1.Hoare法

2.挖坑法

3.前后指针法

4.快排分治

5.关于快排

 6.关于快排的优化

7.总体实现

总结:


快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法

其基本思想为:任待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。(分治思想)

概括快排的思想:
找一个key(基准值),通过交换,使key的左边全小于key,右边全部大于key。这样key就在正确的位置上。重复该过程,直到所有的值都在正确位置上,完成排序。

对比选择排序、插入排序,每次调整无非就第一个元素和最后一个元素在正确位置上。快速排序的单趟排序,可以将调整中间元素,类似一个二叉树的结构。

快排具有高效和广泛的使用,它是最经典的排序之一,并且在各种编程语言的算法库中被广泛使用。

1.Hoare法

Hoare法就是快速排序的创始人Hoare最初的方法,是目前快排中学习成本最高的方法,让我来带大家领略Hoare大佬的思想吧。

快速排序QuickSort,数据结构,数据结构,排序算法,算法
 

单趟排序思想:

左边或者右边第一个位置当作key的位置,本文以左边为例。

双指针Left和Right。Right先走,Right找小,找到了停下。Left再走,Left找大,找到了停下,交换Left和Right的值。Right再走找小,Left找到,交换......直到二者相遇,交换key和相遇点的值。这样的一趟排序后key就在正确的位置上。

下图解释单趟排序的过程:

快速排序QuickSort,数据结构,数据结构,排序算法,算法

本趟排序,使左边的元素都比key小,右边的元素都比key大。从而使key在正确的位置上。

单趟排序的实现:

// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    int keyi = left;
    while (left < right)
    {
        while (left < right && a[right] >= a[keyi])
        {
            right--;
        }
        while (left < right && a[left] <= a[keyi])
        {
            left++;
        }
        Sweap(&a[left], &a[right]);
    }
    Sweap(&a[keyi], &a[left]);
    keyi = left;
    return keyi;
}

快速排序QuickSort,数据结构,数据结构,排序算法,算法

 关于单趟排序的俩个问题:

1.a[right]一定要>=a[key]?a[right]>a[keyi]行吗?

不行。当出现L 和 R同时遇到与K相同的元素时,会出现死循环。

快速排序QuickSort,数据结构,数据结构,排序算法,算法

 2.如果没有越界条件left<right

会出现栈溢出。如果出现极端情况下,key是最小的数,R就会一直减,出现栈溢出。

快速排序QuickSort,数据结构,数据结构,排序算法,算法

Hoare法的快速排序是坑比较多,但是他的思想是非常的高超。领略Hoare的方法,在理解代码起巨大的作用。

2.挖坑法

找一个key为坑,假定左边第一个元素为坑,R.L双指针指向左右,R找小,把坑的值填给R中,R形成新坑,L找大,直到L R相遇,把key值给坑。key就在正确位置上

下面动图展示:

快速排序QuickSort,数据结构,数据结构,排序算法,算法

 由于挖坑法的思路较简单,就不画图演示。

下面展示挖坑法的单趟实现:

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int key = a[left];
    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;
}

 快速排序QuickSort,数据结构,数据结构,排序算法,算法

 挖坑法与Hoare的思想差不多,二者殊途同归。

3.前后指针法

前后指针法的思路:定义key prev cur指针

cur找小,找到了++prev 交换prev和cur的值。cur再走,在交换,直到cur>=n,交换prev和key的值

下面为动图演示:

快速排序QuickSort,数据结构,数据结构,排序算法,算法

单趟排序画图详解:

快速排序QuickSort,数据结构,数据结构,排序算法,算法

 从图中可以看出,将大的元素翻滚式的推到后面。使左边的值全部小于key,右边的值全部大于key。从而key在正确的位置上。

前后指针法单趟排序实现:

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Sweap(&a[cur], &a[prev]);
        }
        ++cur;
    }
    Sweap(&a[keyi], &a[prev]);
    keyi = prev;
    return keyi;
}

前后指针法的实现较为简单,如果能熟练掌握前俩种方法,那么第三种方法便游刃有余。

关于Hoare法的思考:

L 和 R相遇点,会比key大吗?

  不会。相遇的值一定小于key。

1)假设是key在左边,R去遇L,L不动,存在俩种情况 

1.L一直没动,就在key的位置 ,可以直接交换

2.L经过上一轮交换后,已经比key小,相遇后交换必定比key小,可以直接交换

.

2)L去遇R,由于每一轮都是R先走,R找小 找到停下,L去遇R,相遇点就是R停下的位置,一定比key小,可以直接交换。

4.快排分治

每一趟排序后,key在正确位置上,即将数组分成[Left,keyi-1]  keyi  [keyi+1,Right]

后续就要对[Left,keyi-1]  和 [keyi+1,Right]排序即可。

void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;

    int keyi = PartSort2(a, left, right);
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);

}

类似二叉树的前序遍历结构

当最小分割只有一个元素时,(即条件left>=right )停止递归。

5.关于快排

1)时间复杂度

单趟排序:类似满二叉树,树的高度为logN  

整体排序:对N个元素排序,N

总的时间复杂度O(N)=N*log(N)

2)空间复杂度:

最大二叉树的叶子结点为N 空间复杂度为N

3)稳定性

不稳定。快排是通过交换 

例如  3  3  4   2  6  6  单趟排序完 俩个3的次序会发生改变

快排是不稳定的算法。

 6.关于快排的优化

如果key为最小的元素,那么每趟排序都要经过N次 总的时间复杂度为N^2

引入三数取中,找到mid left right 中间大的元素,交换后 以它做key

int GetMidIndex(int *a,int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
            return mid;
        else if (a[right] > a[left])
            return left;
        else
            return right;
    }
    else //a[left]<a[mid]
    {
        if (a[mid] < a[right])
            return mid;
        else if (a[right] < a[left])
            return left;
        else
            return right;
    }
}

7.总体实现

void Sweap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}



int GetMidIndex(int *a,int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
            return mid;
        else if (a[right] > a[left])
            return left;
        else
            return right;
    }
    else //a[left]<a[mid]
    {
        if (a[mid] < a[right])
            return mid;
        else if (a[right] < a[left])
            return left;
        else
            return right;
    }
}

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    int mid = GetMidIndex(a, left, right);
    Sweap(&a[left], &a[mid]);
    
    int keyi = left;
    while (left < right)
    {
        while (left < right && a[right] >= a[keyi])
        {
            right--;
        }
        while (left < right && a[left] <= a[keyi])
        {
            left++;
        }
        Sweap(&a[left], &a[right]);
    }
    Sweap(&a[keyi], &a[left]);
    keyi = left;
    return keyi;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int mid = GetMidIndex(a, left, right);
    Sweap(&a[left], &a[mid]);
    int key=a[left];
    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 mid = GetMidIndex(a, left, right);
    Sweap(&a[left], &a[mid]);
    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi]&&++prev!=cur)
        {
            Sweap(&a[cur], &a[prev]);
        }
        ++cur;
    }
    Sweap(&a[keyi], &a[prev]);
    keyi = prev;
    return keyi;
}


void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;

    int keyi = PartSort2(a, left, right);
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);

}

总结:

关于快排的书写,重点是画好图,多对单趟排序模拟。

Hoare法的难度较大,要多留意。在面试时选择题经常会出现快排的思想。

作者水平有限,如有问题,欢迎探讨。文章来源地址https://www.toymoban.com/news/detail-614594.html

到了这里,关于快速排序QuickSort的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包