【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?,算法,算法,数据结构,排序算法

君兮_的个人主页

即使走的再远,也勿忘启程时的初心

C/C++ 游戏开发

Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容是快速排序的两大优化和非递归实现

  • 好了废话不多说,开始我们今天的学习吧!!

快速排序优化

  • 有关快速排序的基本内容可以去看看这篇博客,讲的已经非常详细了
    【算法速查】万字图解带你快速入门八大排序(下)
  • 我们在这里就以hoare版本的快速排序来讲讲还可以优化的地方以及为什么
  • hoare版本的快速排序代码如下:
Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
int getMid(int* a, int left, int right)
{
    assert(a);
    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
    {
        if (a[mid] < a[right])
            return mid;
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }

    }
}
int PartSort1(int* a, int left, int right)
{
    int mid = getMid(a, left, right);//三数取中
    //把取好的key放到left中
    Swap(&a[left], &a[mid]);
    int key = left;
    while (left<right)
    {
    //右边先走
        while (left < right && a[right] >= a[key])
        {
            right--;
        }
      //左边走
        while (left<right&&a[left]<=a[key])
        {
            left++;
        }
        //交换
        Swap(&a[left], &a[right]);
    }
    //交换停下的位置的值把key换到此时左右相遇的位置
    Swap(&a[key], &a[left]);
    //此时key的左右都有序,由于right,left都指处于key的位置返回任意即可
    return right;
}
void QuickSort(int* a, int left,int right)
{
	//只剩下一个值了,说明已经有序,不需要再排,递归结束
    if (left >= right)
        return;
   
    int key = PartSort1(a,left,right);
    //key已经满足左右都有序了不需要再排
    //排key的左边
    QuickSort(a, left, key-1);
    //排key的右边
    QuickSort(a, key+1, right);

}

三数去中优化

  • 我们知道,快速排序是先取一个key值然后让左右两边有序来进行排序的,因此key值的取值对我们快速排序的速度是有比较大的影响的,举个最坏的例子,假设每次我们取到的key值都是此次所需排序数据中最小的,如下图所示
    【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?,算法,算法,数据结构,排序算法

  • 此时的时间复杂度就是O(N^2)了,因此,我们需要对快速排序进行优化,尽量减少出现图示的这种情况,就有了以下的代码

int getMid(int* a, int left, int right)
{
    assert(a);
    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
    {
        if (a[mid] < a[right])
            return mid;
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }

    }
}
  • 简单的来说,上述这段代码表示的是这样的意思
    取最左,最右,中间三个数,分别对三个数进行比较,最终取得的值就是处于三个值中中间的这个值。
  • 通过上述这个优化,此时所需排序的数据中总要比我们取得的key值小以及比我们取得的key值大的值存在,就能较大的提供我们的快排效率啦!

对递归次数的优化

  • 我们在使用递归版本的快速排序时,当区间中的数比较少时,仍然使用递归的方式进行是会消耗非常多不必要消耗的内存的,还是举个例子:假设此时区间中还有10个数需要排
    【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?,算法,算法,数据结构,排序算法
  • 我们递归返回的条件是left>=right,递归是栈中开辟空间进行的,当递归的层数过深,栈的大小又不是很大,就容易造成“爆栈”,如上图所示,为了排序这十个数,我们又递归了这么多层,是非常不明智的选择,因此,我们在数据较少的情况出现时,可以使用插入排序等方法进行排序,减少不必要的空间浪费,也能提供我们快排的速度
void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	// 小区间优化,小区间不再递归分割排序,降低递归次数
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort1(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort1(a, begin, keyi - 1);
		QuickSort1(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

  • 好了,讲完了上述对递归版本的快排优化,接下来我们讲讲快速排序的非递归版本

非递归的快速排序

  • 我们上面讲了,递归是在栈空间中进行的,栈空间又比较小,当递归层数比较深时就会造成“爆栈”,因此对于快速排序这种我们常用的排序算法来说,掌握其非递归版本也是非常重要的
  • 想要了解非递归,我们就必须从递归开始下手,我们再来看看递归的这段代码
void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	// 小区间优化,小区间不再递归分割排序,降低递归次数
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort1(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort1(a, begin, keyi - 1);
		QuickSort1(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

  • 如果你学过数据结构的话,会发现我们递归与栈是非常类似的,栈是后进先出,最后再处理最先放入的,而递归也是先往深处走,再往回返,因此,我们在实现非递归的快速排序时,选用栈这种数据结构来帮助我们进行。
void QuickSortNonR(int* a, int left,int right)
{
    Stack st;
    StackInit(&st);//初始化栈
    StackPush(&st, left);//入栈
    StackPush(&st, right);
    while (!StackEmpty(&st))//判断栈是否为空
    {
        int right = StackTop(&st);//后进先出,取栈顶元素
        StackPop(&st);//此时的栈顶元素出栈
        int left = StackTop(&st);//此时的栈顶为left
        StackPop(&st);
        int key = PartSort1(a, left, right);//选key值
        if (key + 1 < right)//此时key+1小于right 把key+1作为下一次排序的左 right作为右入栈
        {
            StackPush(&st, key + 1);
            StackPush(&st, right);
        }
        if (left < key - 1)//key-1大于left key-1就为下一次循环的右,left为左
        {
            StackPush(&st, left);
            StackPush(&st, key - 1);
        }

    }
    //当栈中没有元素了,说明此时的左大于等于右,此时已经没有数据未进行排序了
    StackDestroy(&st);//销毁栈
}
  • 和递归大致是一样的,只不过我们是用栈的方式来模拟递归朝深度进行,如果你能理解递归实现的快速排序,相信非递归实现的快速排序对你来说也非常好理解
  • 唯一需要注意的是入栈和出栈的顺序,当你开始先入右再入左的话,由于后进先出的原因,先出的是左其中是右,这点在取栈顶元素作为排序的左右区间时一定要注意避免取错。

总结

  • 好啦,我们总算把八大排序算法都讲完了,算法这一块光靠看代码不是那么容易理解的,因此我花了大量的时间画图分析,希望能对你有所帮助
  • 当然,这篇文章创作的初衷是希望帮助初学者对排序算法有一个大致的了解,对已经学过的人起到在需要使用的时候快速回忆的效果,因此可能还有一部分细节不全,之后我会挑出重点单独出博客讲解
  • 有任何的问题和对文章内容的疑惑欢迎在评论区中提出,当然也可以私信我,我会在第一时间回复的!!

新人博主创作不易,如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力!!!

**(可莉请求你们三连支持一下博主!!!点击下方评论点赞收藏帮帮可莉吧)**

【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?,算法,算法,数据结构,排序算法文章来源地址https://www.toymoban.com/news/detail-720949.html

到了这里,关于【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构与算法之快速排序

    快速排序 (Quick Sort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数

    2024年02月10日
    浏览(43)
  • 【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

    2024年02月08日
    浏览(50)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(52)
  • 【数据结构与算法】快速排序的三种实现方法

      目录 一.基本思想 二.Hoare法 动态演示 三.挖坑法 动态演示 四.前后指针法 动态演示 五.快速排序优化 随机下标交换法 三路取中法 六.快速排序的特性 任取待排序元素序列中的某元素作为 基准值 ,按照该排序码将待排序集合 分割成两子序列 , 左子序列中所有元素均小于基

    2023年04月09日
    浏览(60)
  • 【数据结构与算法】快速排序的非递归实现方法

      目录 一.前言 二.非递归实现 如果数据量过大的话,不断递归就会出现 栈溢出 的现象,这个时候你的代码是没问题的,但就是跑不起来,这个时候就要 把递归改成非递归 。 一般有两种改法: 1.直接改,利用循环等; 2.借助栈的辅助。 而快速排序的非递归实现方法就需要

    2023年04月17日
    浏览(51)
  • 【数据结构】详解七大排序算法(直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序)

    1、基本思想    把待排序的数按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所以的记录插入完为止,得到一个新的有序序列。    实际中我们玩扑克牌时,就用到了插入排序的思想 基本步骤:    当插入第i个元素时,前面的arr[0]、arr[2]…arr

    2024年02月04日
    浏览(72)
  • 数据结构和算法——快速排序(算法概述、选主元、子集划分、小规模数据的处理、算法实现)

    目录 算法概述 图示 伪代码 选主元 子集划分 小规模数据的处理 算法实现 快速排序和归并排序有一些相似,都是用到了分而治之的思想:   通过初步的认识,我们能够知道快速排序算法最好的情况应该是: 每次都正好中分 ,即每次选主元都为元素的中位数的位置。 最好情

    2024年02月15日
    浏览(40)
  • 【数据结构】论如何拿捏快速排序?(含非递归)

    目录 一,快速排序(递归) 1,快排思想 2,霍尔排序 3,挖坑法 4,前后指针法 5,快速排序优化 1,三数取中法选key 2,小区间优化 二,快速排序(非递归) Stack.h Stack.c 三,快速排序源代码 1,快排思想 快速排序是 Hoare于1962年 提出的一种 二叉树结构的交换 排序方法,其

    2024年02月08日
    浏览(57)
  • 【数据结构】- 排序(详细介绍几种排序算法!!!*直接插入排序,*希尔排序,*选择排序,*堆排序,*冒泡排序,*快速排序,*归并排序)

    排序无处不在,所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 内部排序 :数据元素全部放在内存中的排序。 外部排序 :数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。 今天

    2024年01月20日
    浏览(59)
  • 【Java数据结构与算法】Day2-高级排序(希尔、归并、快速、计数)

    ✅作者简介:热爱Java后端开发的一名学习者,大家可以跟我一起讨论各种问题喔。 🍎个人主页:Hhzzy99 🍊个人信条:坚持就是胜利! 💞当前专栏:【Java数据结构与算法】 🥭本文内容:Java数据结构与算法中的比较高级的排序,希尔排序、归并排序、快速排序、计数排序

    2024年02月02日
    浏览(62)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包