【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“

这篇具有很好参考价值的文章主要介绍了【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“,# 排序篇,排序算法,算法,数据结构,c语言,开发语言

🎥 屿小夏 : 个人主页
🔥个人专栏 : 算法—排序篇
🌄 莫道桑榆晚,为霞尚满天!

📑前言

什么是快排?快排的速度到底有多快呢?它们的思想和实现是什么样的?

本文会对这快速排序进行详解,绝对细致入微!让你彻底搞懂快排!

🌤️快速排序的概念

☁️快速排序的由来

英国计算机科学家Tony Hoare在1960年为了解决计算机上的排序问题,提出了快速排序的算法,最初是为了在英国的英尔兰电子公司(ELLIOTT Brothers)的快速硬件上实现高效的排序算法。

☁️快速排序的思想

快速排序的主要思想是分治法,将一个大问题分割成小问题,解决小问题后再合并它们的结果。

☁️快速排序的实现步骤

  1. 从待排序的数组中选择一个元素,称之为枢纽元(pivot)。
  2. 将数组中小于枢纽元的元素移到枢纽元的左边,将大于枢纽元的元素移到枢纽元的右边,这个过程称为分区(partition)。
  3. 递归地对枢纽元左边的子数组和右边的子数组进行排序。
  4. 当所有子数组都有序时,整个数组就自然有序了。

🌤️快速排序(递归版)

☁️快排主框架

void QuickSort(int* a, int left, int right)
{
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
	if (right <= left)
		return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
	//int keyi = PartSort1(a, left, right);
	//int keyi = PartSort2(a, left, right);
	int keyi = PartSort3(a, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, keyi-1) 和 [keyi+1, right)
// 递归排[left, keyi-1)
	QuickSort(a, left, keyi - 1);
// 递归排[keyi+1, right)
	QuickSort(a, keyi + 1, right);
}

上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,在写递归框架时想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

☁️Hoare版本快排

⭐代码与图解

【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“,# 排序篇,排序算法,算法,数据结构,c语言,开发语言

int PartSort1(int* a, int left, int right)
{
	//三数取中(优化)
	//int keyi = NumBers(a, left, right);
	//Swap(&a[keyi], &a[left]);
	int key = left;

	while (left < right)
	{
		while (left < right && a[left] <= a[right])
		{
			right--;
		}
		while (left < right && a[left] <= a[right])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);
	return left;
}

⭐代码解析:

  1. 首先,定义一个变量key,用于保存基准值的下标,初始值为left。
  2. 进入一个循环,循环条件是left < right,即左右指针没有相遇。
  3. 在循环中,首先从右边开始,找到第一个小于等于基准值的元素的下标,将right指针左移,直到找到符合条件的元素或者left和right相遇。
  4. 然后从左边开始,找到第一个大于基准值的元素的下标,将left指针右移,直到找到符合条件的元素或者left和right相遇。
  5. 如果left < right,说明找到了需要交换的元素,将a[left]和a[right]交换位置。
  6. 重复步骤3到步骤5,直到left和right相遇。
  7. 最后,将基准值a[key]和a[left]交换位置,将基准值放在正确的位置上。
  8. 返回分割点的下标left。

实现了一次快速排序的分割操作,将数组分成两部分,左边的元素都小于等于基准值,右边的元素都大于基准值。然后再通过递归调用这个函数,这就是hoare版的快排。

☁️挖坑法

⭐代码与图解

【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“,# 排序篇,排序算法,算法,数据结构,c语言,开发语言

int PartSort2(int* a, int left, int right)
{
	//三数取中优化
	//int keyi = NumBers(a, left, right);
	//Swap(&a[keyi], &a[left]);
	int key = a[left];
	int hole = left;//为第一个坑

	while (left < right)
	{
		while (left < right && key <= a[right])
		{
			--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;
}

⭐代码解析:

  1. 定义一个变量key,用于保存基准值,初始值为a[left]。
  2. 定义一个变量hole,用于保存空洞的位置,初始值为left。
  3. 进入一个循环,循环条件是left < right,即左右指针没有相遇。
  4. 在循环中,首先从右边开始,找到第一个小于基准值的元素的下标,将right指针左移,直到找到符合条件的元素或者left和right相遇。
  5. 将a[right]的值赋给a[hole],将空洞的位置移动到right。
  6. 然后从左边开始,找到第一个大于基准值的元素的下标,将left指针右移,直到找到符合条件的元素或者left和right相遇。
  7. 将a[left]的值赋给a[hole],将空洞的位置移动到left。
  8. 重复步骤4到步骤7,直到left和right相遇。
  9. 最后,将基准值key放入空洞的位置a[hole],将基准值放在正确的位置上。
  10. 返回空洞的位置hole。

同样实现了将数据分成两部分,左边的元素都小于等于基准值,右边的元素都大于基准值。

☁️双指针法

⭐代码与图解

【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“,# 排序篇,排序算法,算法,数据结构,c语言,开发语言

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	//三数取中优化
	//int midi = NumBers(a, left, right);
	//Swap(&a[left], &a[midi]);

	int prev = left;
	int cur = prev + 1;

	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	return prev;
}

⭐代码解析

  1. 定义两个指针prev和cur,分别指向left和left+1。
  2. 定义一个变量keyi,用于保存基准值的下标,初始值为left。
  3. 进入一个循环,循环条件是cur <= right,即cur指针没有越界。
  4. 在循环中,如果a[cur]小于基准值a[keyi],则将prev指针右移一位,并交换a[prev]和a[cur]的值,保证prev指针之前的元素都小于基准值。
  5. 将cur指针右移一位。
  6. 重复步骤4到步骤6,直到cur指针越界。
  7. 最后,将基准值a[keyi]和a[prev]交换位置,将基准值放在正确的位置上。
  8. 返回分割点的下标prev。

同样实现了将数据分成两部分,左边的元素都小于等于基准值,右边的元素都大于基准值。

☁️三数取中优化

⭐为什么要三数取中?

  1. 三数取中是为了选择一个更好的基准值,以提高快速排序的效率。在快速排序中,选择一个合适的基准值是非常重要的,它决定了每次分割的平衡性。

  2. 快速排序是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的小,然后再对这两部分分别进行快速排序,递归地进行下去,直到整个序列有序。

  3. 如果每次选择的基准值都是最左边或最右边的元素,那么在某些情况下,快速排序的效率可能会降低。例如,当待排序序列已经有序时,如果每次选择的基准值都是最左边或最右边的元素,那么每次分割得到的两个子序列的长度差可能会非常大,导致递归深度增加,快速排序的效率降低。

  4. 而通过三数取中的优化,可以选择一个更好的基准值,使得每次分割得到的两个子序列的长度差更小,从而提高快速排序的效率。

  5. 具体来说,三数取中的优化是选择待排序序列的左端、右端和中间位置的三个元素,然后取它们的中值作为基准值。这样选择的基准值相对于最左边或最右边的元素,更接近整个序列的中间位置,可以更好地平衡分割后的两个子序列的长度,从而提高快速排序的效率。

  6. 通过三数取中的优化,可以减少递归深度,提高分割的平衡性,使得快速排序的效率更稳定,适用于各种不同的输入情况。

⭐三数取中代码实现

//三数取中
int NumBers(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	// left mid right
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])  // mid是最大值
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right]) // mid是最小
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

☁️小区间优化

⭐什么是区间优化?

小区间优化是指在快速排序中,当待排序的子序列的长度小于一定阈值时,不再继续使用快速排序,而是转而使用直接插入排序。

⭐小区间优化代码实现

void QuickSort(int* a, int left, int right)
{
	if (right <= left)
		return;
	if(right - left + 1 > 10)
	{
        int keyi = PartSort3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	else
	{
		InsertSort(a + left,right - left + 1);
	}
}

⭐小区间优化的好处

  1. 减少递归深度:使用插入排序来处理较小的子序列,可以减少递归的深度,从而减少了函数调用的开销。
  2. 提高局部性:插入排序是一种稳定的排序算法,它具有良好的局部性,可以充分利用已经有序的部分序列。对于较小的子序列,插入排序的效率更高。
  3. 减少分割次数:对于较小的子序列,使用插入排序可以减少分割的次数。快速排序的分割操作需要移动元素,而插入排序只需要进行元素的比较和交换,因此在较小的子序列中使用插入排序可以减少分割操作的次数。

小区间优化可以在一定程度上提高快速排序的性能。它通过减少递归深度、提高局部性和减少分割次数来优化算法的效率,特别适用于处理较小的子序列。

🌤️快速排序(非递归版)

这里需要借助栈的来实现非递归.关于栈详情见:数据结构剖析–栈

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	StackInit(&st);
	StackPush(&st, right);
	StackPush(&st, left);

	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort3(a, begin, end);
		if (keyi + 1 < end)
		{
			StackPush(&st, end);
			StackPush(&st, keyi + 1);
		}
		if (begin < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}
	StackDestroy(&st);
}

☁️代码解析

  1. 将整个序列的起始和结束位置入栈。然后,进入循环,不断从栈中取出子序列的起始和结束位置。
  2. 在每次循环中,通过PartSort3函数将当前子序列分割成两部分,并得到基准值的下标keyi。如果基准值右边的子序列长度大于1,则将右边子序列的起始和结束位置入栈。如果基准值左边的子序列长度大于1,则将左边子序列的起始和结束位置入栈。
  3. 循环继续,直到栈为空,表示所有的子序列都已经排序完成。

通过使用栈来模拟递归的过程,非递归实现避免了递归调用的开销,提高了快速排序的效率。

🌤️快速排序的特性总结

  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序

  2. 时间复杂度:O(N*logN)【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“,# 排序篇,排序算法,算法,数据结构,c语言,开发语言

  3. 空间复杂度:O(logN)

  4. 稳定性:不稳定

🌤️全篇总结

​ 本章对快排从其思想到实现,一步步由浅入深的讲解,相信聪明的你看到这里已经对快排有一个明白的理解了!

看到这里希望给博主留个:👍点赞🌟收藏⭐️关注!

【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“,# 排序篇,排序算法,算法,数据结构,c语言,开发语言文章来源地址https://www.toymoban.com/news/detail-742683.html

到了这里,关于【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【Linux】shell编程基础(超详细,入门看这一篇就够了)

    🥇🥇【Liunx学习记录篇】🥇🥇 篇一:【Linux】VMware安装unbuntu18.04虚拟机-超详细步骤(附镜像文件) 篇二:【Linux】ubuntu18.04系统基础配置及操作 篇三:【Linux】用户与组的操作详细介绍 篇四:【Linux】管理Linux文件权限属性介绍 篇五:【Linux】使用数字表示法和文件表示法修

    2024年02月04日
    浏览(44)
  • 【Java面向对象】多态的详细介绍,简单易懂,看这一篇就够了

    A: 方法或对象具有多种形态,是面向对象的第三大特征,多态是建立在封装和继承的基础之上的。简单来说,多态是具有表现多种形态的能力的特征。 消除类型之间的耦合关系 可替代性 可扩充性 接口性 灵活性 简化性 重载式多态在编译时已经确定好了。方法名相同而参数

    2024年01月20日
    浏览(66)
  • Linux Vim的使用(超详细,只看这一篇就足够了!)

    开篇先上 vim 键盘神图 1)Vim 中的5种编辑模式 在命令行中执行 vim filename ,若 filename 已存在,则 filename 被打开显示其内容;若 firename 不存在,则Vim在第一次存盘时自动在硬盘上新建filename文件。 vim有5种模式:命令模式、输入模式、末行模式、可视化模式、查询模式。 1.命令

    2024年02月06日
    浏览(49)
  • Verilog:【7】超详细WaveDrom教程,时序图绘制利器,看这一篇就够了。

    碎碎念: 没想到上一篇发出去,前几个小时竟然基本没人看,是我写得太晦涩了吗,这篇介绍个简单但是相当好用的软件WaveDrom,可以非常方便的绘制时序图,简直是数字人的福音啦! 本文将从安装开始,详细介绍涉及到的语法等内容,读者可以收藏起来随时查阅。 P.S. 照这

    2024年02月03日
    浏览(48)
  • 耗时80小时!超详细的胎教级Stable Diffusion使用教程,看这一篇就够!

    大家好,用爷爷都能听懂的方式分享可以落地实操的干货 花了很长时间终于整理好了这份SD的使用教程! 从手把手安装部署,到界面功能讲解,再到实战案例制作,到下载优质模型,每一步都有详细教程 并且用一个又一个的例子展示,让大家不止是枯燥地看,而是看完立刻

    2024年01月17日
    浏览(54)
  • QT入门看这一篇就够了——超详细讲解(40000多字详细讲解,涵盖qt大量知识)

    目录 一、Qt概述 1.1 什么是Qt 1.2 Qt的发展史 1.3 Qt的优势 1.4 Qt版本 1.5 成功案例 二、创建Qt项目 2.1 使用向导创建 2.2 一个最简单的Qt应用程序 2.2.1 main函数中 2.2.2 类头文件 2.3 .pro文件 2.4 命名规范  2.5 QtCreator常用快捷键 三、Qt按钮小程序 3.1按钮的创建和父子关系 3.2 Qt窗口坐标

    2024年02月09日
    浏览(45)
  • SQL SERVER数据库:SQL看这一篇就看够了(附详细代码及截图)

    目录 写在前面 01-SQL SERVER 数据库基础 02_01-创建数据库 02_02-创建数据表 02_03-表结构和约束的维护 03-插入数据 04-数据的修改和删除 05-基本查询 06_01-条件查询一 06_02-条件查询二 07-模糊查询 08-聚集函数 09-分组查询 10-多表查询一 11-多表查询二 本篇文章是在下面这个B站课程里学

    2024年02月04日
    浏览(50)
  • 【Python系列】Python教程合辑-史上最全最详细-从入门到入土,看这一篇就够了

    目录 Python合辑汇总列表 用Python自动办公,做职场高手【完结】     玩转Python3入门到精通视频教程     数据分析资料包  全民一起玩Python     千锋教育Python700集零基础入门到精通(爬虫 办公自动化 数据分析)     慕课网实战课-畅销3年的Python分布式爬虫课程-原版提取  

    2024年02月22日
    浏览(87)
  • 最优化算法对偶单纯形法的matlab实现(对偶单纯形法看这一篇就够了)

    最优化算法对偶单纯形法的matlab实现: 要读懂本文代码需要了解:nchoosek,setdiff,eye等函数在matlab中的作用,以及/符号在矩阵运算中的作用。 在高等教育出版社《最优化方法》一书中提到的单纯形法表格如下图所示: 其中:c为目标函数系数, A为约束方程组系数矩阵, b为约

    2023年04月16日
    浏览(39)
  • 精通线程池,看这一篇就够了

    当我们运用多线程技术处理任务时,需要不断通过new的方式创建线程,这样频繁创建和销毁线程,会造成cpu消耗过多。那么有没有什么办法 避免频繁创建线程 呢? 当然有,和我们以前学习过多连接池技术类似,线程池通过提前创建好线程保存在线程池中, 在任务要执行时取

    2023年04月17日
    浏览(90)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包