快速排序1(hoare版本)

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

一、什么是快速排序?

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

二、快速排序hoare版本

hoare版本是快速排序最原始的版本,是hoare大佬最先提出的一种快排的方法。
其基本思想为:先选取数组左边的第一个数作为key,定义一个左下标left指向最左边的数,定义一个右下标right指向最右边的数,然后让right先往左遍历寻找一个比key小的数字,找到后停下来;再让left向右遍历寻找一个比key大的数字,找到后停下来(简单理解为左边找比key大的,右边找比key小的),然后把找到的这两个数交换,然后right再向左找小,left向右找大,再交换,以此类推,直到left和right相遇,再把这个相遇的位置的数字和key交换就完成了一趟快速排序。经过了一趟快速排序之后,key的值就来到了key最终有序是该出现的位置,因为左边是比它小的,右边是比它大的,它的位置就是正确的。然后再把key的左边和右边作为一个局部的数组重复上面的步骤,直到每一个局部区间都是有序的,那么这个数组也就是有序的了。
切记:左边做key,必须要让右边先走,这样才能保证相遇位置的左边的数比key小,右边的数比key大,证明如下:

快速排序1(hoare版本)

情况一、
快速排序1(hoare版本)

快速排序1(hoare版本)
情况二、
快速排序1(hoare版本)
快速排序1(hoare版本)
情况三、
快速排序1(hoare版本)
快速排序1(hoare版本)

left和right相遇的地方有以上三种情况,可以看到,(左边做key,让右边先走),无论是哪一种情况都能保证相遇的位置的数一定是小于等于key的,所以和key交换就一定能保证key的左边比key小(或者等于),右边比key大。
但是如果左边做key,左边先走呢?我们也来看一看下图。
快速排序1(hoare版本)
快速排序1(hoare版本)
所以左边做key,让右边先走是必然的;相反,右边做key,让左边先走也是必然的。

上面的演示都是只进行了一趟快排,要想完成整个数组的排序还需要以key的位置为分界点,左边的子数组和右边的子数组也分别递归做同样的快速排序,直到区间内只剩下一个值(left==right)或者区间不存在(left>right)就停止,这样就能使每一个区间的子数组都是有序的,最终整个数组也就变成有序了。

但是这样每次都选左边做key的话,如果数组是有序的,假如是升序,那么在每一趟子数组的快排里,最左边的值就是最小的,那每一次从right开始向左找比key小的数都要找到最左边的和key相等的数,这样的话排序执行的次数就变成了n+ n-1 + n-2+…+3+2+1,那么时间复杂度就变成了O(N^2)了,这显然是不合理的,所以大佬又想出了两个优化的方法:

其一、随机选key。
生成一个属于数组内的随机下标,那么这个下标对应的数大概率不会是最大或者最小的数,因为这是随机生成的,然后用这个数和left下标(即最左边)的数进行交换,这样的话left对应的数就是一个趋近于这个数组中间的数了。那选这个数做key就能够更好地提高每一趟快速排序的效率了。

其二、 三数取中。
就是对比排序数组(可能是子数组)的最左边,中间,最右边的三个数,取不是最大也不是最小的一个的那一个数,使它和left位置的数交换之后做key,那么这个key就不可能出现极端(最大/最小)值的情况了,这比随机选key要更好那么一点,因为随机选key还是会取到最大值或者最小值做key的。

参考代码如下:

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//三数取中
int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		//来到这里证明a[mid]最小,那么a[left]和a[right]
		//谁小谁就是中间的那个数
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else//a[left]<=a[mid]
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		//来到这里证明a[mid]最大,那么a[left]和a[right]
		//谁小谁就是中间的那个数
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
//小区间优化需要用到直接插入排序
void InsertSort(int* a, int n)
{
	assert(a);
	int i = 0;
	int end = 0;
	int tmp = 0;

	for (i = 0; i < n - 1; i++)
	{
		end = i;
		tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

// 快速排序hoare版本
//给定一个数组和数组的左右下标进行快速排序
int PartSort1(int* a, int left, int right)
{
	//随机选key
	//int randi= left + (rand() % (right - left));
	//Swap(&a[left], &a[randi]);
	
	//三数取中
	int mid = GetMidNumi(a, left, right);
	//如果left就是取到的数,那么也就没有必要交换了
	if (mid != left)
	{
		Swap(&a[left], &a[mid]);
	}
	//三数取中只是调整最左边值的大小,
	//三数取中交换之后依然是选左边作为
	//keyi,但是此时这个key就不会是
	//数组中的最大值或者最小值了,为了
	//优化有序数组的情况
	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		
		//用左边大的和右边小的进行交换,使小的数翻到前面
		//大的数翻到后面
		Swap(&a[left], &a[right]);
		
	}
	//最后把key和相遇的位置的数交换(这里写a[left]和a[right]都是一样的,因为相遇地方left==right)
	Swap(&a[keyi], &a[left]);
	keyi = left;

	return keyi;

}


void QuickSort(int* a, int left,int right)
{
	assert(a);
	//区间只有一个值或者区间不存在就不用再递归下去了
	if (left >= right)
	{
		return;
	}
	//这里进行一个小区间优化,当一个区间<=10个元素的时候
	//快排已经不再适合,因为快排是数据越多并且越乱的时候
	//才是越快的,但是数据量小的时候,快排是没有很大的优势
	// 的如果这个是一个大数组经过多次递归下来的小区间,证明
	// 这个区间接近于有序的,此时换成直接插入排序会更加的高效
	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right + 1 - left);
	}
	else
	{
		//每一趟快排之后都返回keyi的位置,把区间分成
		//[left,keyi-1][keyi][keyi+1,right]三个部分
		//再对子区间的数组进行快排,直到不满足递归条件再返回
		int keyi = PartSort3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}

}

三、快速排序的时间复杂度是多少?

快速排序的时间复杂度为O(N*logN)。
证明如下:
快速排序1(hoare版本)

最后来上一张完整演示的动图:
快速排序1(hoare版本)

以上就是hoare版本的快速排序,你学会了吗?如果你感觉到有所收获的话,那就动动你的小手给博主点点小心心,点点关注呗!剩下两个版本的快速排序,我们下期再聊!!!文章来源地址https://www.toymoban.com/news/detail-402826.html

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

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

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

相关文章

  • C语言版--单链表排序,冒泡排序,选择排序,插入排序,快速排序,应有尽有,保证看懂,没有bug!交换节点版本!

    你好                 如果复制时发现有缩进报错,后者空格报错等问题,以VScode为例,可以按Ctrl+F,复制一个报错的空格,然后替换成一个手打的空格键,具体操作可以搜搜,可以看我的博客。 具体截图:以 12 34 78 56 23 99 34 12 45 76为例,其他朋友可以自己举 选择排序

    2024年02月03日
    浏览(36)
  • Java实现快速排序

    一.原理 快速排序算法通过多次比较和交换来实现排序,其排序流程如下:   (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。  (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右

    2024年02月09日
    浏览(40)
  • 快速排序Java

    快速排序是在工具类常用的排序算法,快速排序的思想主要是选定一个基准元素,然后找到基准元素的位置,然后再分别排序他左边的和他右边的,快速排序是不稳定的,时间复杂度位Nlog(N),最极端的情况就是一个反向排好顺序的数组,然后每次二分都分不开导致的时间复杂度

    2024年02月08日
    浏览(30)
  • 【JAVA】快速排序

    快排,和冒泡排序一样,是同一类型的排序,都是交换排序 交换,涉及在遍历中比较,然后相互交换元素 冒泡排序是根据趟数两两比较,边比较边交换,快排也一样,不过冒泡是以顺序表的格式进行的,而快排则是建立在二叉树的基础上来完成遍历交换的~(个人理解) 快排

    2024年02月01日
    浏览(29)
  • 快速排序(java代码)

    快排核心思想就是:首先在待排序数组中随便选择一个数作为节点(pivot),然后从最后面(high)往左查找比这个节点(pivot)小的数,并且从最前面(low)往右查找比这个节点(pivot)大的数(low),情况1:找到后就把这两个数进行交换,然后接着上面的查找交换直到low等

    2024年02月12日
    浏览(39)
  • Java 快速排序

    快速排序是一种常用的基于比较的排序算法,其时间复杂度为 O(nlogn),并且具有稳定性和广泛的应用场景。本文将全面详细的讲解一下 Java 中快速排序算法的原理、实现以及时间复杂度等问题。 快速排序是一种分治思想的排序算法,其基本原理可以概括为以下三步: 选取一

    2024年02月10日
    浏览(47)
  • 快速排序【Java算法】

    快速排序是一种比较高效的排序算法,采用 “分而治之” 的思想,通过多次比较和交换来实现排序,在一趟排序中把将要排序的数据分成两个独立的部分,对这两部分进行排序使得其中一部分所有数据比另一部分都要小,然后继续递归排序这两部分,最终实现所有数据有序

    2024年02月14日
    浏览(51)
  • Java基础(十一)快速排序

    快速排序的思想 快速排序(QuickSort)是一种高效的排序算法,基于分治策略。它的原理可以概括为以下步骤: 选择一个基准元素(pivot),通常选择数组中的一个元素作为基准。这个基准元素将用来将数组分割为较小和较大的两个子数组。 分区过程(Partition):将数组中的

    2024年02月13日
    浏览(38)
  • 六大排序算法(Java版):从插入排序到快速排序(含图解)

    目录 插入排序 (Insertion Sort) 直接插入排序的特性总结: 选择排序 (Selection Sort) 直接选择排序的特性总结 冒泡排序 (Bubble Sort)  冒泡排序的特性总结 堆排序(Heap Sort) 堆排序的特性总结 希尔排序 (Shell Sort)   希尔排序的特性总结 快速排序(Quick Sort) Hoare版  挖坑法  前后指

    2024年02月09日
    浏览(51)
  • 【数据结构】深入浅出理解快速排序背后的原理 以及 版本优化【万字详解】(C语言实现)

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

    2024年02月05日
    浏览(100)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包