(排序5)快速排序(Hoare,选key的随机数与三数取中优化,挖坑法与前后指针法等)

这篇具有很好参考价值的文章主要介绍了(排序5)快速排序(Hoare,选key的随机数与三数取中优化,挖坑法与前后指针法等)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

快速排序 (Hoare大佬版本)

  1. 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中
    的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右
    子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
  2. 快速排序的单趟排序是这样的,首先是先要选出一个基准值/关键值key,然后再把这个数组当中所有比key小的数放到key的左边;再把这个数组当中所有比key大的数放到key的右边(弄完了之后,实际上也从侧面变相的说明:此时此刻key自己已经处在正确的位置上,也就是说排好序之后最终要去的位置)。
  3. 一般来说,这个基准值都是选择这个数组当中最左边的或者最右边的。
  4. 快速排序的单趟排序:快速排序的单趟排序也在排一个数,也就是说确定一个数的最终位置。但是他的单趟排序之外还附加了一个效果。就是说比key小的数在这么一次单趟排序之后全部在key所在位置的左边,比key大的数道理一样在右边。相当于还做了分割的这么一个功能。
  5. 关键结论:左边当key,让右边就先走;右边当key,让左边先走。这是一个结论,这样子做的目的就在于当左右指针相遇的时候,确保在相遇的这个位置的值是比key要小,正是因为有了这个确保,才可以进行交换。因此为什么需要这样?就是因为确保在相遇位置的那个值与key能够交换并且能够保证分割部分规律性不会破坏。
  6. 右指针找小,左指针找大,然后两者都到达既定位置之后,把两者所指向的位置的数给它调换一下。交换完了之后再继续向中间走。然后直到两个指针相遇,这时候就把相遇位置的数值与key进行交换。
//快速排序单趟排序
int keyi = left;
while (left < right)
{
	while (arr[right] > arr[keyi])
	{
		right--;
	}
	while (arr[left] < arr[keyi])
	{
		left++;
	}
	Swap(arr + left, arr + right);
}
Swap(arr + left, arr + keyi);
  1. 是上面这个写法吗?不是的,错误百出。排雷:当左右两个指针分别在进行找大与找小的操作的时候,不能直接在while循环判断条件里面单独大于号或者小于号,如果这样子的话可能会出现死循环。所以说都必须得加上等于号。这样子的话就可以说明,比如说我在找小的时候,我是真的在找小;找大的时候,我是真的在找大。也就是说比如说我的左右指针碰到了与key相等的情况,这时候就直接无视继续向中间走。在快速排序的单趟排序当中,我们知道规则就是说把比key小的数放到左边,然后比key大的数放到右边。至于那些与key相等的数的话,在左边右边都无所谓,因此当左右指针碰到与key相等的数的时候直接无视继续走,所以说等号必须得加到while循环的判断条件当中。这是第一点。
  2. 然后在里面的两个并列的while循环的判断条件里面必须得加上left<right,不然会有大坑,因为这样的话,也在某些特殊情况的话会飘出去,会发生越界。正确代码为:
//快速排序单趟排序
int keyi = left;
while (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 + left, arr + keyi);
  1. 快速排序的单趟排序完成之后,这时候key就已经不需要再去动了。接下来就是递归操作。这边声明一下:左指针的下标是left,右指针的下标是right,然后选中的关键值为key,关键值的下标是keyi
  2. 快速排序的单趟排序本质上也是在排一个数据,使那个数据key通过这个单趟排序落在正确的位置上。当单趟排序完成之后,接下来就是通过递归操作,需要递归两次。然后既然QuickSort是个递归函数,那么一开始在这个函数的开头必须得限制一下递归结束的条件。如果说当前这个数据段只有一个数据,那就没必要进行快排;或者说索性当前这个区间根本就不存在,那就更加没有必要进行快排。因此在函数开头得限定一下递归结束条件:left>=right,那么这时候就退出来。代码如下:
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	//快速排序单趟排序开始
	int keyi = left;
	while (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 + left, arr + keyi);
	//快速排序单趟排序结束

	keyi = left;
	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}

快速排序的时间复杂度与优化的铺垫引入

  1. (排序5)快速排序(Hoare,选key的随机数与三数取中优化,挖坑法与前后指针法等)
  2. 假设在快速排序当中,以理想化的方式看待,就是说在每一个单趟排序完成之后,那个key就最终落在当前最中间的位置。
  3. 所有比key小的数落在他的左边,所有比key大的数落在他的右边。然后接下来就不断进行递归。然后你结合一下这个图,你会发现这个与二叉树非常的相似。在整个总的递归过程当中,大概有logN层。
  4. 然后在每一层当中,各个左右指针总共走的一个次数也大概都是在O(N)这个级别。虽然在实际上来讲,每一层的话左右指针总共走的次数肯定是在不断递减,因为随着越来越多的key值的最终正确位置被确定下来,所需要递归在处理的区间也在不断的缩小。但不管怎么样,由于时间复杂度统计的是一个量级,并不需要特别精确的计算。
  5. 因此总而言之,对于每一层而言,它的总共的遍历总数还是O(N)这个级别。再加上总共有logN层,所以说快速排序的时间复杂度为NlogN
  6. 而且根据图像我们可以发现,递归的深度为logN,这个就十分的友好,基本上不用考虑栈溢出的情况。因为就算这个n为100万,那么再加上log之后,也就变成了20左右,算个啥。
  7. 但上面讲的都是理想情况,接下来比如说举两个例子,当前需要排序的数组已经是升序有序或者降序有序,在这种情况下面执行上述快速排序代码的时候,根据图像可以发现此时它的递归深度为N,这就非常的隐患,当数据量一大的时候,非常容易发生栈溢出,因为他递归的深度不是之前理想情况下的logN,其次可以发现总的遍历的次数一个等差数列的相加,因此是O(N^ 2)。就算没有栈溢出的情况之下,N^2的效率也非常慢。(排序5)快速排序(Hoare,选key的随机数与三数取中优化,挖坑法与前后指针法等)
  8. 由此可以发现影响快速排序性能与递归深度的就是单趟排序之后key的所在位置。如果说在这个每次单趟排序之后,key总能够尽量的接近于中间位置,也就是说在递归的时候越能够进行二分,越二分的话就越接近满二叉数,越接近满二叉树的话深度就显得更加均匀,与此同时深度越均匀的话,效率也就越高。如果在当前的数据已经是有序或者说接近有序的情况之下。那么无论是递归的深度还是整个快速排序的效率都将会打折扣。(我这边都是默认在选择最左边当作key的情况之下
  9. 因此,key的选取就需要优化一下,不能老是选择最左边的,不然会有效率低下与栈溢出的隐患。(排序5)快速排序(Hoare,选key的随机数与三数取中优化,挖坑法与前后指针法等)

快速排序(Hoare大佬版本 + 选key随机数优化法) (randi ----> left ----> 之前的逻辑)

  1. 因此归根到底就在于单趟排序之后key的所在位置
  2. 在快速排序当中没有硬性规定这个基准值到底必须在哪里。于是这时候有一种新的方法,就是说去随机的选key。
  3. 其实也相当于就是用生成随机数的方法,在生成随机数的同时必须得保证这个随机数一定是落在这个区间里面。为了保证生存的随机数一定是在参数的left,right这两个左右边界之内,于是生成随机数的时候不能直接rand(),要这样left + rand() %(right-left).
  4. 然后保持之前代码的逻辑不变,还是让最左边的那个值当key,不过并不是真正让原先最左边的那个字作为关键值,而是让新生成的随机数这个下标所在的值作为key,这时候就非常简单,只需要在随机数生成之后,把随机数指向的那个值与最左边的那个值交换一下就可以
  5. 在这种随机选key的情况之下,不管你原先是有序还是没有序,尤其假设原先你是有序的状态,但经过这么随机选key之后,就给他强行打乱了,至少这个key在单趟排序最终落在的位置是不这么靠近边边角角,那也就意味着更加接近于二分了。
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	//快速排序单趟排序开始
	int randi = left + rand() % (right - left);
	Swap(arr + left, arr + randi);

	int keyi = left;
	while (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 + left, arr + keyi);
	//快速排序单趟排序结束

	keyi = left;
	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}

快速排序(Hoare大佬版本 + 选key三数取中优化法) (midi ----> left ----> 之前的逻辑)

  1. 还有一种选择key的方法就是三数取中,就是说把你当前这个需要排序的数组的头和尾巴拿出来,然后再把中间的那个值给他拿出来,然后三个数进行比较。然后选择那个既不是最大的也不是最小的那个值当成基准值。然后把基准值找到之后,我再跟最左边的换一下。这样子就又好比最左边的那个值就是基准值了,然后就接下来就可以套用原先的那个逻辑。
  2. 在原先这个数组是有序或接近有序的情况之下,三数取中优化会变得非常的棒。比随机数优化还要更加明显。
  3. 如果说原先这个数组也是随机的话,经过测试,总体而言三数取中还是比随机数优化要更加好一点。
  4. 对于三数取中与随机数优化取key而言,这时候这个快速排序基本上不存在最坏情况。我们说快速排序它的时间复杂度NlogN,但是实际上在某些特殊情况会跑到N^2这个级别,但是他还有的救,通过三数取中选key等优化就可以抢救一下。
  5. 所以说在快速排序当中不看最坏,不是因为搞特权,而是因为可以加优化,所以说快速排序的时间复杂度就是NlogN
int GetMidNumi(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] < arr[right] ? mid : right;
		}
	}
	else
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] > arr[right] ? mid : right;
		}
	}
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	//快速排序单趟排序开始
	int midi = GetMidNumi(arr, left, right);
	Swap(arr + left, arr + midi);


	int keyi = left;
	while (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 + left, arr + keyi);
	//快速排序单趟排序结束

	keyi = left;
	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}

关于单趟排序中的为什么左边为key,要右指针先走的解释

  1. 之前有个关键的结论:就是说如果key选择最左边的那个数,那么左右指针必须是右指针先走,这样做的目的就是能够确保当左右指针相遇的时候,在相遇点那个值一定是比key要小(以升序排列为例),正是因为如此,就可以把相遇点那个值与key进行交换。如果说key选择最右边的,那么道理是一样的…接下来就解释一下具体的原因:
  2. 以最终目的升序排列为例,左边当key,右边先走,这样子就能保证最终相遇位置比key小;右边当key,左边先走,这样子就能保证最终相遇位置比key要大。
  3. 首先必须得知道就“相遇”而言,分为两种情况:第一种就是说是相遇前最后一幕:右边先走,因为右指针是找小,然后找到小之后就停下来不动了,然后左指针开始向右偏移去找大(每一轮都是右指针开始先走),但左指针找大没有找到,然后与右指针碰到了,这时候相遇位置的值很显然是比key要小。
  4. 刚才是左指针遇到右指针,有没有可能是右指针遇到左指针呢?也是有可能这个就是第二种情况。就是说相遇前最后一幕:就是说右指针不断向左偏移去找小,结果还没有找到直接碰到了左指针,这时候也可以去推断出左指针此时此刻指向的值更是比key小,因为在上一轮的交换过程当中,已经把比key小的值交换到此刻的左指针位置了,哪怕就是在最开始的话,无非就是最后直接到keyi位置,也就是key自己与自己交换。
  5. 所以说以升序排列为例:就是说如果key选择最左边的那个数,那么左右指针必须是右指针先走,这样做的目的就是能够确保当左右指针相遇的时候,在相遇点那个值一定是比key要小(以升序排列为例),正是因为如此,就可以把相遇点那个值与key进行交换。(排序5)快速排序(Hoare,选key的随机数与三数取中优化,挖坑法与前后指针法等)

快速排序 (挖坑法,选key默认三数取中优化)

  1. 首先还是得搞清楚单趟排序的目的,就是把比key小的数赶到左边去,把比key大的数赶到右边去。
  2. 首先先把基准值保存到一个临时的变量当中,然后基准值所在的那个位置就形成了一个坑。然后右指针开始出发去找小,找到比key小的数之后就把它甩到那个坑当中,然后自己这边形成了一个新的坑;然后左指针开始向右偏移找大,找到之后甩到右边的那个坑里面,如此循环。然后左右指针一定相遇在坑里。
  3. 然后相遇的时候,把那个基准值放到那个最后那个两者相遇所在的坑里面。
  4. 挖坑法的话,相当于在原先的Hoare大佬方法的递归结构是保持不变的,只不过是在单趟排序的地方做了一些稍微改动而已。
int GetMidNumi(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] < arr[right] ? mid : right;
		}
	}
	else
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] > arr[right] ? mid : right;
		}
	}
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	//快速排序单趟排序开始
	int midi = GetMidNumi(arr, left, right);
	Swap(arr + left, arr + midi);

	int hole = left;
	int key = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;

		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;

	QuickSort(arr, begin, hole - 1);
	QuickSort(arr, hole + 1, end);
}

快速排序 (前后指针法,选key默认三数取中优化)

  1. 这种方法的话相当于用了一前一后的两个指针prev, cur ,或者说叫做下标。
  2. 首先就是cur一直往后走,然后当cur指向一个比key小的值的时候,先把prev++,然后把cur与prev位置上的值给他交换一下。然后cur++,总而言之cur是需要一直向右不断的走。
  3. prev要么紧跟着cur(间隔为0,真一前一后),要么prev与cur中间间隔着比key大的一段值区间。然后到cur在不断向右走的过程中去找小,相当于就是把比key大的这段值区间感觉在不断的向右推,然后把比key小的数给他翻到左边去。
  4. 然后当cur不断向右偏移的时候,最终会超出原先的数据范围。然后对于prev有个规律,就是他的后面一个马上也就是比key大的数了,所以也就是说他本身指向的是比key小的数据。所以在最后,就是把prev所指向的数值与key进行交换。(排序5)快速排序(Hoare,选key的随机数与三数取中优化,挖坑法与前后指针法等)
int GetMidNumi(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] < arr[right] ? mid : right;
		}
	}
	else
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] > arr[right] ? mid : right;
		}
	}
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	//快速排序单趟排序开始
	int midi = GetMidNumi(arr, left, right);
	Swap(arr + left, arr + midi);
	int keyi = left;

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

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

	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}

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

到了这里,关于(排序5)快速排序(Hoare,选key的随机数与三数取中优化,挖坑法与前后指针法等)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Hutool 生成随机数和随机字符串

    官方文档: https://www.hutool.cn/docs/#/core/工具类/随机工具-RandomUtil 整理完毕,完结撒花~

    2024年02月16日
    浏览(54)
  • MySQL、Oracle 生成随机ID、随机数、随机字符串

    UUID():是由128位的数字组成的全局唯一标识符。每次都生成一个新的随机数。 它通常以32个十六进制数的形式表示,分为5个部分,以连字符分隔。 UUID的长度是36个字符,包括32个十六进制数字和4个连字符。 UUID的标准格式是由 8-4-4-4-12 个十六进制数字组成的,其中每个部分的

    2024年01月16日
    浏览(56)
  • Python 获取随机数

    作用:随机生成一个[0,1)之间的浮点数 作用:随机生成[a, b]范围内一个整数 作用:随机生成[a, b]范围内一个整数,如果指定step,step作为步长会进一步限制[a,b]的范围,比如randrange(10, 20, 2)表示生成[10, 20)范围内的随机偶数 作用:产生[a, b]范围内一个随机浮点数 作用:从数组

    2024年02月14日
    浏览(37)
  • 生成随机数

    用于产生随机数 boolean nextBoolean() : 返回下一个伪随机数,它是取自此随机数生成器序列的均匀分布的 boolean 值。 void nextBytes(byte[] bytes) : 生成随机字节并将其置于用户提供的 byte 数组中。 double nextDouble() : 返回下一个伪随机数,它是取自此随机数生成器序列的、在 0.0 和 1.0 之

    2024年02月03日
    浏览(51)
  • Flutter 生成随机数

    如何让随机数变化? 我们尝试过的都知道,当你创建出来一个随机数后,调用他他的值是随机的,但是,这时候他的值就会固定住,不管怎么样都是随机出来的那个数,如果想要他每次都不一样的话,我们就想要使用刷新来让他变化了。 我们可以使用这样的方法来使他每次不一

    2024年02月13日
    浏览(44)
  • haiku生成随机数

    Haiku 遵循 JAX 的设计,生成的随机数是两个元素组成的列表。其中第一个元素是用于生成伪随机数的状态,第二个元素是用于分发密钥的子键。两个元素分别用于状态和子键,确保在分布式计算或并行计算中,多个随机数生成器的状态可以在一定程度上相互影响,从而提高随

    2024年01月20日
    浏览(60)
  • 一文详解安全随机数

    本文分享自华为云社区《【安全攻防】深入浅出实战系列专题-安全随机数》,作者: MDKing 。 使用随机数可分类安全场景跟非安全场景。非安全场景需要生成的越快越好。安全场景使用的随机数必须足够安全,保证不能被预测到。 常见的非安全场景: 数据的索引号、标识;

    2024年02月05日
    浏览(45)
  • 真伪随机数

    随机数生成的方式一般有两种,分别为: 硬件生成随机数Hardware RNG,原理是用某个仪器一直探测环境中的物理量(比如说,时钟,IO 请求的响应时间,特定硬件中断的时间间隔,键盘敲击速度,鼠标位置变化,甚至周围的电磁波等等……直观地讲,你每按一次键盘,动一下鼠

    2024年02月10日
    浏览(36)
  • 随机数算法,SQL

    记录 id      权重 1       5 2       10 3       50 4      100 找权重最大的那个值,调用rand()函数,它会随机生成一个0-1的值 然后 rand * 100 得出一个随机值  它的范围  0 =  随机值   100 例如本次随机值为2,那么找到 大于2的所有记录,然后升序 此时查询结果为 2     

    2024年02月09日
    浏览(35)
  • mysql随机数函数

    declare@iint select@i=count(*)fromA while@i0 begin UpdateAsetB=ceiling(rand()*150+50)whereid=@i set@i=@i-1 id是表A里的自增长列,不清楚你的表里有没有,若是没有的话,可以自己造个临时表,插入数据。 本回答由提问者推荐 UUID是一个由5位十六进制数的字符串表示的128比特数字,其格式为aaaaaaaa-

    2023年04月11日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包