八大排序算法之快速排序(下篇)(快排的优化+非递归快排的实现)

置顶努力的青菜

已于 2023-04-05 12:46:07 修改

阅读量1.6k

点赞数 46

分类专栏：初阶数据结构文章标签：排序算法数据结构算法

于 2023-03-22 19:05:58 首次发布

本文链接： https://blog.csdn.net/weixin_73470348/article/details/129675164

版权

初阶数据结构专栏收录该内容

18 篇文章 6 订阅

订阅专栏

一.前言

1.快速排序的实现:

快速排序的单趟排序(排升序)(快慢指针法实现):

2.未经优化的快排的缺陷

二.快速排序的优化

1.三数取中优化

优化思路:

2. 小区间插入排序优化

小区间插排优化的递归快排:

三.非递归快速排序的实现

1.快排一个难以避免的缺陷(暂不考虑三指针单趟排序优化)

2.非递归快排的实现思路

数据结构栈模拟系统栈算法思想:

非递归快排代码实现:

一.前言

1.快速排序的实现:

🤪快排的详细实现原理参见青菜的博客🤪: http://t.csdn.cn/0bf1ghttp://t.csdn.cn/0bf1g下面简单回顾一下快排的核心思想:

快速排序的单趟排序(排升序)(快慢指针法实现):
int PartionV3(int* arr, int left, int right)//完成1个元素的排序,同时分割数组
{
	assert(arr);
	int key = left;										//选取数组左端元素作为key值
	int slow = left;								    //slow从left开始  
	int fast = left + 1;							    //fast从left+1开始遍历数组
	while (fast <= right)
	{
		if (arr[fast] < arr[key])			//fast找到比key小的值
		{
			++slow;				   			//slow指向下一个位置
			if (slow != fast)				//fast和slow相等没必要交换
			{
				swap(&arr[slow], &arr[fast]);//交换slow和fast所指向的值
			}
		}
		++fast;							 //fast遍历数组
	}
	swap(&arr[key], &arr[slow]);         //最后交换key和slow所指向的变量
	return slow;  						 //返回slow位置下标
}
🤪假设乱序数组有N个元素,则需要进行N趟单趟排序(每次单趟排序可以完成一个key元素在有序序列中的归位)
🤪直接循环N-1次单趟排序的时间复杂度为O(N^2)
🤪为了降低排序的时间复杂度的数量级,我们采用分治递归思想来完成这N次单趟排序
🤪基本思想是:每次单趟排序完成后,以被归位的key元素为划分点,将数组划分为在排序意义上互不关联的两个子数组(左子数组中每个元素都比key小,右子数组中每个元素都比key大),从而使得后续每次单趟排序需要遍历的元素个数呈指数式递减,总体排序的时间复杂度也因此降阶,递归过程中数组被逐步划分过程的图示:(划分结构逻辑上类似于二叉树)

上图中每个数组拆分层次中(一个拆分层次中有多个子数组),单趟排序所需遍历的总的元素个数的数量级为O(N),拆分层次的数量级为O(logN),因此上述情形下,快排的总体时间复杂度为O(NlogN).

😜这里我们假设所处理的数组都是逆序数极大的乱序序列:这种情况下,每次单趟排序所确定的数组分割点有极大的可能是在数组的中间位置。
😜对应上图完成排序的分治递归代码:
//每完成一次数组分割,就进行左右子数组分治递归完成每一个元素的排序
void QuickSort2(int* arr, int left, int right)
{
	assert(arr);
	if (left>=right)							    //子数组只剩1个元素时(或left和right错开时)停止递归
	{
		return;
	}
	int breakpoint = PartionV3(arr, left, right);	//找到数组分割点(同时也完成了一个元素的排序)
	//左右子数组分治递归
	QuickSort(arr, left, breakpoint - 1);     //处理左子数组
	QuickSort(arr, breakpoint + 1, right);    //处理右子数组
}
😜注意递归结束条件的控制😜