快速排序【hoare版本】【挖坑法】【双指针法】(数据结构)

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

       快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

一、hoare版本

       该算法的大体框架为:假设取数组的头为key同时保存索引变量begin的值在此处,取key的另一端为索引变量end,end不断向左移动,直至处于一个小于key的值的位置,此时再让索引变量begin不断向右移动,直至处于一个大于key的值的位置,交换两个值。由此不断循环往复,最终肯定会在一个大于key值的位置处end和begin相遇,最终交换该值与key所在的位置,即可得到一个左边比key小,右边比key大的一个数组。

       由于数组是以key为基准,左右两边分别小于和大于key,所以该数组又可分为[left,key-1] , [key+1,right],然后递归调用上面的算法,左右子序列重复该过程,直至所有元素都排列在相应位置上即可。

下图为单趟快速排序的过程

快速排序【hoare版本】【挖坑法】【双指针法】(数据结构),数据结构,数据结构,排序算法,算法,c语言,c++

程序源代码

//单趟排序
int PartSort1(int* a, int begin, int end)
{
	int key = a[begin];//选取左边做key
	int keyindex = begin;
	while (begin < end)
	{
		while (begin < end && a[end] >= key)//此处必须要在此判断begin<end,防止end越界
		{
			end--;
		}
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		Swap(&a[end], &a[begin]);
	}
	//此时begin == end
	Swap(&a[end], &a[keyindex]);//此处不能跟key交换,因为key是局部变量
	return begin;
}
void QuickSort(int* a, int left , int right)
{
	assert(a);
	if (left >= right)
	{
		return;
	}
	int div = PartSort1(a, left, right);
	//[left,div - 1]  div  [div + 1 , right]
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}

注意事项

1.若选取右边的值做key,那么一定要让左边的begin先走,这样能保证他们性欲的位置一定是一个比key大的位置...(选取左边值做key同理)

2.注意在移动begin和end的时候每次都需要判断begin<end,防止begin和end相遇之后错过,无法进行正确的排序

优化

       经过分析我们发现:快速排序的最坏情况是每次选择的基准元素都是当前子数组的最大或最小值,导致每次划分只能减少一个元素的规模。在这种情况下,算法的时间复杂度接近于O(N*N),快速排序也就没有什么优势了,因此我们要做出优化。 

       为避免选取到最大值或者最小值,出现了三数取中法。即选取三个数的中间值作为基准,就可以很好地避免这种情况。改进后的代码变为:

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

}
//单趟排序
int PartSort1(int* a, int begin, int end)
{
	int midindex = GetMidIndex(a, begin, end);
	Swap(&a[midindex], &a[begin]);

	int key = a[begin];//选取左边做key
	int keyindex = begin;
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		Swap(&a[end], &a[begin]);
	}
	//此时begin == end
	Swap(&a[end], &a[keyindex]);//此处不能跟key交换,因为key是局部变量
	return begin;
}
void QuickSort(int* a, int left , int right)
{
	assert(a);
	if (left >= right)
	{
		return;
	}
	int div = PartSort1(a, left, right);
	//[left,div - 1]  div  [div + 1 , right]
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}

 二、挖坑法

       挖坑法是最主流的快速排序的方法,因为其易于理解。挖坑法,顾名思义,就是要把数据挖出来,假设以最左端位置为坑,把它的值保存在一个变量key内,定义索引变量begin和end,使end不断向左边移动,直至a[end]的值小于key,把它放在坑内,然后begin再向右移动,直至a[begin]的值大于key,把它放在a[end]的坑内。由此循环往复,我们可以得到一个与上面排序相同的结果。

程序源代码

/挖坑法
int PartSort2(int* a, int begin, int end)
{
	int midindex = GetMidIndex(a, begin, end);
	Swap(&a[midindex], &a[begin]);
	
	int key = a[begin];//坑
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[begin] = a[end];
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[end] = a[begin];
	}
	//begin == end
	a[begin] = key;
	return begin;
}
void QuickSort(int* a, int left , int right)
{
	assert(a);
	if (left >= right)
	{
		return;
	}
	int div = PartSort3(a, left, right);
	//[left,div - 1]  div  [div + 1 , right]
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}

注意事项

在移动begin和end的时候,同样要每次判断begin是否小于end,防止begin和end错过

三、双指针法

双指针法相对来说较难理解一点。我们要取最后一个元素为key,定义两个变量cur,prev,其中cur是数组的首元素的索引(begin),prev位于数组首元素的前一个位置,即begin - 1。算法的思想是:cur向右不断移动,直至找到a[cur] < key,++prev,然后让prev所在位置与cur所在位置的值进行交换。依次重复这个过程,我们也可以得到跟上面两种方法相同的结果。

程序源代码

//双指针法
int PartSort3(int* a, int begin, int end)
{
	int midindex = GetMidIndex(a, begin, end);
	Swap(&a[midindex], &a[begin]);

	int key = a[end];
	int cur = begin;
	int prev = begin - 1;
	while (cur <= end)
	{
		while (cur<= end && a[cur] >= key)//注意!!!
		{
			cur++;
		}
		if (cur <= end)
		{
			prev++;
			Swap(&a[cur], &a[prev]);
			cur++;
		}
	}
	Swap(&a[++prev], &a[end]);
	return prev;
}
void QuickSort(int* a, int left , int right)
{
	assert(a);
	if (left >= right)
	{
		return;
	}
	int div = PartSort3(a, left, right);
	//[left,div - 1]  div  [div + 1 , right]
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}

代码也可以换一种形式来呈现:

//双指针法
int PartSort3(int* a, int begin, int end)
{
	
	int prev = begin - 1;
	int cur = begin;
	int keyindex = end;
	while (cur <= end)
	{
		if (a[cur] < a[keyindex] && a[cur] != a[keyindex])
		{
			Swap(&a[cur], &a[++prev]);
		}
		cur++;
	}
	Swap(&a[keyindex], &a[++prev]);

	return prev;
}
void QuickSort(int* a, int left , int right)
{
	assert(a);
	if (left >= right)
	{
		return;
	}
	int div = PartSort3(a, left, right);
	//[left,div - 1]  div  [div + 1 , right]
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}

注意事项

在初始化prev的值时,不能将其初始化为-1,要初始化为begin-1。初始化为-1,会导致子数列在进行递归时出现问题。 


今天的分享到这就结束了,欢迎持续关注,有问题可以私信交流~文章来源地址https://www.toymoban.com/news/detail-792201.html

到了这里,关于快速排序【hoare版本】【挖坑法】【双指针法】(数据结构)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • ​​快速排序(四)——挖坑法,前后指针法与非递归

    目录 ​一.前言 二.挖坑法 三.前后指针法 四.递归优化 五.非递归 六.结语   本文我们接着上篇文章的重点快排,现在继续讲解对快排优化的挖坑法,前后指针法以及非递归方法,下面是上篇文章快排链接:https://mp.csdn.net/mp_blog/creation/editor/135719674。 码字不易,希望大家多多支

    2024年01月24日
    浏览(33)
  • 全网最全的快速排序方法--Hoare快排 挖坑法快排 二路快排 三路快排 非递归快排

    目录 一.快速排序 1.基本介绍 2.基本思想 二.Hoare快排 0.前情知识 1.交换数组中的两个元素 2.指定范围的插入排序 1.基本思路 2.代码实现 3.优化思路 三.挖坑法快排(校招中适用) 1.基本思路 2.代码实现 四.二路快排 1.基本思路 2.代码实现 3.优化思路 五.三路快排 1.基本思路 2.代码

    2023年04月21日
    浏览(41)
  • 快速排序1(hoare版本)

    快速排序(英文名:Quicksort,有时候也叫做划分交换排序)是一个高效的排序算法,由Tony Hoare在1959年发明(1961年公布)。当情况良好时,它可以比主要竞争对手的归并排序和堆排序快上大约两三倍。这是一个分治算法,而且它就在原地排序。即不需要额外开辟空间,仅仅是

    2023年04月08日
    浏览(28)
  • C++数据结构与算法——双指针法

    C++第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C++查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更新,欢迎关注! 给你一个数组 nums 和一个值 val,你需要 原地

    2024年02月20日
    浏览(38)
  • 【每日算法 && 数据结构(C++)】—— 01 | 平方值去重统计(解题思路STL法,双指针法、流程图、代码片段)

    “Success is not final, failure is not fatal: It is the courage to continue that counts.” - Winston Churchill (成功并非终点,失败并非致命:真正重要的是继续前行的勇气 - 温斯顿·丘吉尔) 给你一个整数数组,数组中的数可以是正数、负数、零,请实现一个函数,返回这个数组中所有数的平方

    2024年02月12日
    浏览(51)
  • 快速排序(三)——hoare法

    目录 ​一.前言 二.快速排序 hoare排法​ 三.结语 本文给大家带来的是快速排序,快速排序是一种很强大的排序方法,相信大家在学习完后一定会有所收获。 码字不易,希望大家多多支持我呀!(三连+关注,你是我滴神!) 快速排序是Hoare与1962年提出的一种二叉树结构的交

    2024年01月22日
    浏览(42)
  • 双指针法的应用场景

    目录 一、二分查找 二、移除元素 三、x的平方根 四、删除链表的倒数第N个节点 五、长度最小的子数组 六、链表相交 七、反转字符串 八、环形链表II 九、三数之和 十、四数之和 题目地址:力扣 题目地址:力扣 题目地址:力扣 题目地址:力扣 题目地址:力扣 题目地址:

    2024年02月11日
    浏览(77)
  • 10 快速排序-左右指针法

    void QuickSort(int *arr, int begin, int end) {         if (begin = end)         {                 return;         }         int left = begin;         int  right = end;         int key = begin;         while (begin end)         {                 while (endbegin arr[end] = arr[key])                 {    

    2024年01月21日
    浏览(50)
  • C语言实现快排核心思想(双指针法)

     核心代码: 这就是每一趟快排的实现代码,由上面的动图,我们能知道前后指针法的核心是玩好cur和prev这两个指针,具体的逻辑是cur找比key小的值,找到就prev++,然后prev和cur的值就进行交换,但是总不能自己跟自己交换吧,这就是多此一举了,所以我们在代码中的if语句里

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

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

    2024年02月08日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包