【数据结构与算法】快速排序的三种实现方法

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

【数据结构与算法】快速排序的三种实现方法

 文章来源地址https://www.toymoban.com/news/detail-406809.html

目录

一.基本思想

二.Hoare法

动态演示

三.挖坑法

动态演示

四.前后指针法

动态演示

五.快速排序优化

随机下标交换法

三路取中法

六.快速排序的特性


一.基本思想

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

二.Hoare法

假设我们让最左边为keyi(注意这个表示的是下标),且要排升序;

1.若最左边为keyi,则right先走,找比arr[keyi]小的,left后走,找比arr[keyi]大的,然后right与left交换;

   当left和right相遇时,结束循环,最后交换arr[keyi]和arr[left]

   再让keyi=left,接着递归它的左子列和右子列

2.若最右边为keyi,则left先走,找比arr[keyi]大的,right后走,找比arr[keyi]小的,然后right与left交换

   当left和right相遇时,结束循环,最后交换arr[keyi]和arr[left]

   再让keyi=right,接着递归它的左子列和右子列

注意这里的keyi,left,right都是下标

左子列的区间是begin到keyi-1

右子列的区间是keyi+1到end

【数据结构与算法】快速排序的三种实现方法

 

动态演示

【数据结构与算法】快速排序的三种实现方法

 

void QuickSort(int* arr, int left,int right)
{
	
	if (left >= right)
		return;
	int begain = left;
	int end = right;
	int keyi= left;
	while (left < right)
	{
        //这里要先判断left<right,防止越界,下同
		while (left<right && arr[right]>=arr[keyi])   //找小
		{
			right--;
		}

		while (left < right && arr[left] <= arr[keyi])  //找大
		{
			left++;
		}

		Swap(&arr[left], &arr[right]);   //交换
	}

	Swap(&arr[keyi], &arr[left]);
	keyi = left;

	QuickSort(arr, begain, keyi-1);   //递归左子列
	QuickSort(arr, keyi+1, end);      //递归右子列
}

三.挖坑法

动态演示

【数据结构与算法】快速排序的三种实现方法

上面的Hoare法有很多坑,一不注意就容易写错,而挖坑法就没那么多坑了。

这个方法需要定义一个坑变量(hole),前面的Hoare法是交换两个元素,挖坑法是把值赋给坑位,然后更新一下坑位 。

void QuickSort(int* arr, int left, int right)
{

	if (left >= right)
		return;
	int begain = left;
	int end = right;
	int keyi = left;
	int hole = left;   //坑变量
	while (left < right)
	{
		while (left < right && arr[right] >= arr[leyi])   //找小
		{
			right--;
		}
		arr[hole] = arr[right];   //赋值给坑位
		hole = right;   //更新坑位
		while (left < right && arr[left] <= arr[keyi])   //找大
		{
			left++;
		}

		arr[hole] = arr[left];
		hole = left;
	}

	arr[hole] = key;
	keyi = left;
    //递归左右子列
	QuickSort(arr, begain, hole - 1);
	QuickSort(arr, hole + 1, end);
}

四.前后指针法

动态演示

【数据结构与算法】快速排序的三种实现方法

这个方法可以说是实现快速排序最常用的方法了。

1.定义一个prev和cur,它们都表示数组的下标,当然你定义成指针也没问题,这里以下标为例;

2.cur=prev+1

  注意:

           a.prev要么紧跟着cur,即prev的下一个就是cur;

           b.prev跟cur中间隔着比key大的一段值区间;

3.cur找到比key小的值,prev++,cur和prev位置互换,cur++

4.cur找到比key大的值,cur++

5.当cur>right时结束循环。 

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int begin = left, end = right;
	int prev = left, cur = left + 1;

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

		while (arr[cur] > arr[keyi])
		{
			cur++;
		}
	}
	Swap(&arr[keyi], &arr[prev]);
	keyi = prev;
	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}

五.快速排序优化

在面对有序或是接近有序的情况下,快速排序的效率不高,是O(N^2),那要怎么解决这个问题呢?

【数据结构与算法】快速排序的三种实现方法

 

既然对有序或是接近有序的不行,那我们就打乱它的顺序,这里有两种方法:

1.通过生成区间内的随机下标,让keyi与randi的数据交换,这样就打乱了原来的顺序;

2.三路取中法。

随机下标交换法

int randi = left + rand() % (right - left);   //随机key
Swap(&arr[keyi], &arr[randi]);

三路取中法

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

	}

}

	if (left != midi)
		Swap(&arr[left], &arr[midi]);

六.快速排序的特性

1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(logN)
4. 稳定性:不稳定


🐬🤖本篇文章到此就结束了,若有错误或是建议的话,欢迎小伙伴们指出;🕊️👻

😄😆希望小伙伴们能支持支持博主啊,你们的支持对我很重要哦;🥰🤩

😍😁谢谢你的阅读。😸😼

【数据结构与算法】快速排序的三种实现方法

 

到了这里,关于【数据结构与算法】快速排序的三种实现方法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(62)
  • 数据结构与算法:快速排序

    荷兰国旗问题 想要理解快速排序,就先理解这个问题: [LeetCode75.颜色分类] 荷兰国旗是由红白蓝三色组成的: 现在将其颜色打乱 然后根据一定的算法,将其复原为红白蓝三色,这就叫做荷兰国旗问题。 在LeetCode的题目中,其将荷兰国旗的三个颜色用0,1,2来表达,也就是说

    2024年01月15日
    浏览(42)
  • 【数据结构与算法】:选择排序与快速排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:腾讯云 欢迎来到排序的第二个部分:选择排序与快速排序! 选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最

    2024年03月17日
    浏览(52)
  • 今天我们来说说常用的三种排序算法:选择排序、插入排序、快速排序

    原文链接:http://www.ibearzmblog.com/#/technology/info?id=8ac4902f82f525e1456624d5d7a545dc 选择排序、插入排序、快速排序这三种算法算是比较初级的排序算法,对它们的原理和技巧,可以方便我们对后面的算法理解。 温馨提示,因为动图不好弄,所以我在网上下载了AlgorithmMan来进行动图演示

    2024年02月16日
    浏览(40)
  • 数据结构与算法之快速排序

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

    2024年02月10日
    浏览(43)
  • 【数据结构初阶】十、快速排序(比较排序)讲解和实现(三种递归快排版本 + 非递归快排版本 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】九、排序的讲解和实现(直接插入 希尔 直接选择 堆 冒泡 -- C语言)

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

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

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

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

    2024年03月24日
    浏览(53)
  • 【数据结构】稀疏矩阵存储的三种方法及三元组表示稀疏矩阵转置算法的两种实现 —— C++

    1. 三元组顺序表数据结构 注意:data[]中的元素是按行存储或者按列存储的,所以 在将三元组逆置时,不能简单地将行列下标对换,data[]数组中元素的顺序也需要重新排列 2. 三元组表示稀疏矩阵转置算法1 3. 三元组表示稀疏矩阵转置算法2:快速转置 为了 便于随机存取任意一

    2024年02月05日
    浏览(43)
  • 【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容是快速排序的两大优化和非递归实现 好了废话不多说,开

    2024年02月08日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包