快速排序(三)——hoare法

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

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

目录

​一.前言

二.快速排序

hoare排法​

三.结语


一.前言

本文给大家带来的是快速排序,快速排序是一种很强大的排序方法,相信大家在学习完后一定会有所收获。

码字不易,希望大家多多支持我呀!(三连+关注,你是我滴神!)

二.快速排序

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

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

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

今天我们来学习的是第一种版本:

hoare排法​

下面是动态图例: 

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

开始解析: 

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

简单点讲就是我们找到一个数成为key,然后从右边出发找到比key小的数(如5)

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

然后左边再出发找比key大的数(如7)

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

然后让这两个值交换,意义是把比key小的值尽量放左边,比key大的值尽量放右边

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

交换完之后呢,右边再继续找小(如4)

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

左边也继续找大(如9)

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

然后两者再进行交换

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

再继续找小(如3)

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

再继续找大,但没找到反而相遇了,那就停下

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

然后最让key与相遇的位置交换

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

最后我们发现比key小的都在其左边,比key大的都在右边了。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

右边找比key小的值找到后停下换左边找比key大的值然后也停下最后二者交换,直到key到达最终位置。

所以单趟的意义就是使key到达正确(排好序要放的位置)

老规矩,我们先来分析一下单趟排序代码:

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

那不妨想一想如果key左边5个数有序,右边4个数也有序,那么就完成排序的目的了。

而这又与我们之前学习的二叉树遍历很像,根,左子树,右子树遍历,再对左子树进行分割根,左子树,右子树遍历——前序遍历。

当我们把这个想象成二叉树分治遍历,那么就是排序全部完成的时候了。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

我们可以快速来一遍单趟,设3为key,然后右边找小(2),左边找大(没找到相遇了),与key交换。 

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

3不用动了,再分割出左边选一个key出来。 

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法​ 

继续右边找小(找不到)交换。 

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法​ 

我们把它看成二叉树,当排好最后一组时开始往回递归,遇到key为2的一组时再往右递进,发现是空子树回归,然后继续往上到key为3的一组,对其右子树(5 4 )继续递进。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

至此,左边排序已经排好了。 

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法​ 

 这样对右子树(6右边的排序)持续下去结束后,整个数组的排序完成。

 接下来是代码部分:

int PartSort(int* a, int left, int right)
{
	int key = a[left];
	while (left < right)
	{
		//找小
		while (a[right] > key)
		{
			right--;
		}
		//找大
		while (a[left] < key)
		{
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(key, &a[left]);
	return left;
}

我们定好key下标,首先当left与right相遇的时候(left==right)才会让key交换,所以我们第一层循环用的是left<right。

然后是找大和找小我们第二层循环就正常比较大小++和--就行了。

我们作好大体框架再从细节处出发(找bug):

当我们修改数组中的2个数字再次排序时。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

我们会发现left与right都会在6这个位置停下,这样造成的结果就是死循环!

所以我们需要修改条件

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

而在我们处理好上面这个问题后又会出现新问题:数组越界 

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

可以发现如果是如图中数组,那么right就会不断--移出数组外造成越界问题。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

所以需要添加条件(让right--时遇到left就停下,避免越界),left同理。 

int PartSort(int* a, int left, int right)
{
	int key = a[left];
	while (left < right)
	{
		//找小
		while (left<right && a[right] >= key)
		{
			right--;
		}
		//找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&key, &a[left]);
	return left;
}

还有一个问题:当key发生交换的时候只是数值发生了交换,但key还是在原来的位置,所以我们需要把它移动到交换后的位置。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

这样就可以

int PartSort(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++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

接下来就是处理分治问题: 

void QuickSort(int* a, int begin, int end)
{
	int keyi = PartSort(a, begin, end);
	//[begin,keyi-1]key[keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

然后我们需要制定一个结束的条件:

  • 只有一个数的时候(left==right)结束
  • 没有数的时候(left>right)
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);
	//[begin,keyi-1]key[keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

下面这是递归展开图: 

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

我们来用100万个随机数来测试一下快排的性能

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

可以看到快排的效率是名不虚传的~

在我们写完快排后再来回顾几个问题:

为什么相遇的位置一定比key小呢?

如果相遇的位置比key大,那交换肯定是会出问题的。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

我们重新按原位置开始走,当快要相遇时,在R先走的情况下 ,能让R停下的是比key小的3。这样是让L走然后与R相遇。验证了R先走,相遇值比key小。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

如果一开始是L先走,走到同样情景时,因为是L先走它会去找比key大的数,就这样找到了9,也与R相遇,但这样最后交换是错误的,相遇的位置比key大。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

我们再换一种情况,把3换成10:

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

我们会发现如果是R先走,那么它会找小,最后越过10找到了4并与L相遇.因为L的位置一定是比key小的数字,毕竟它下标对应的数字是由R(负责找比key小的数字)找到并交换过来的。验证了R先走,相遇值比key小。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

如果是L先走呢?在10停下后等R相遇然后交换,最后发现交换是错误的,因为出现了左边(10)比key(6)大的情况,相遇值比key大。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

最后是一种极端情况:在几乎是升序的数组里R从右边先走直到和L相遇,相遇的位置没有比key小。交换后对其右边的一组数值再进行分治划分,

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法​ 

经过这几种情况分析我们可以发现,如果是L先走然后相遇值都是比key大的,并且交换都会出现错误。而在R先走然后相遇值都是比key小的,并且交换不会出现错误。

相信大家应该发现了,key在左边的时候我们就让右边先走,key在右边的时候我们让左边先走。

因为当key在左边的时候我们要确保最后的相遇值是比key小的,这样交换过来才能符合升序的规则,所以我们让R先走确保它找到的值一定是小的。同理key在右边时我们要确保交换过来的相遇值要比key大,这样才能符合升序规则,而让L先走就一定能确保它找到的是比key大的值。

最终我们需要学会根据key的位置不同,升序降序的规则不同合理作出相应的变化~

下面我们来分析快排的第二个问题:快排的效率分析

假设我们每一次选出的key都是中位数就会呈现出这种情况

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

我们可以看到每一层的单趟排序其实都可以看作是N次执行(在数很多的情况下),因为每一层合计起来也差不多是N这个量级。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

而它的高度是logN,这样它的总的时间复杂度度就是O(N*logN)

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

但这只是比较理想的情况下,如果是在接近有序的情况下,它的高度就会变成N,这样时间复杂度的就会是O(N^2)

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

为了避免快排在有序的情况下效率受到干扰,我们设置了一个叫三数取中的方法。(不是位置取中,而是数值取中)

改变选key的策略,不再是固定选左边的值作key,但如果是中间的值作key又是先走左边还是右边呢,这样也会影响到单趟排序。其实我们可以一直选左边的值作key,就算你选到的key在中间把它换到左边就行了。

这样无论是有序还是无序最终key的交换落点都能尽量落到与下图差不多的位置,避免了有序时算法效率的损耗。

快速排序(三)——hoare法,数据结构,数据结构,c语言,算法,排序算法

最终代码: 

int GetMidi(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;
		}
	}
}


int PartSort(int* a, int left, int right)
{
	int midi = GetMidi(a,left,right);
	Swap(&a[midi], &a[left]);
	int keyi = left;
	while (left < right)
	{
		//找小
		while (left<right && a[right] >= a[keyi])
		{
			right--;
		}
		//找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);
	//[begin,keyi-1]key[keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

三.结语

本次我们介绍了hoare的快排法,相信大家都发现了有很多的坑点需要我们注意,不过放心,下一篇文章我会介绍在原基础上优化更加的其他快排法~最后感谢大家的观看,友友们能够学习到新的知识是额滴荣幸,期待我们下次相见~文章来源地址https://www.toymoban.com/news/detail-814363.html

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

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

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

相关文章

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

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

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

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

    2024年03月17日
    浏览(53)
  • 数据结构与算法之快速排序

    快速排序 (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日
    浏览(54)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

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

    2024年03月24日
    浏览(55)
  • 【数据结构】—从冒泡排序丝滑过度快速排序(含C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波:靴の花火—ヨルシカ            

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

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

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

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

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

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

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

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

    2024年02月04日
    浏览(77)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包