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

03-15 1458阅读 0评论

$八大排序算法之快速排序(下篇)(快排的优化+非递归快排的实现),八大排序算法之快速排序(下篇)(快排的优化+非递归快排的实现),词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,接口,比较,第1张$

（图片来源网络，侵删）

一.前言

1.快速排序的实现:

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

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

二.快速排序的优化

1.三数取中优化

（图片来源网络，侵删）

优化思路:

2. 小区间插入排序优化

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

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

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

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

（图片来源网络，侵删）

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

非递归快排代码实现:

一.前言

1.快速排序的实现:

🤪快排的详细实现原理参见青菜的博客🤪:http://t.csdn.cn/0bf1g $八大排序算法之快速排序(下篇)(快排的优化+非递归快排的实现),词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,接口,比较,第5张$ http://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)							    //子数组只剩1个元素时(或left和right错开时)停止递归
	{
		return;
	}
	int breakpoint = PartionV3(arr, left, right);	//找到数组分割点(同时也完成了一个元素的排序)
	//左右子数组分治递归
	QuickSort(arr, left, breakpoint - 1);     //处理左子数组
	QuickSort(arr, breakpoint + 1, right);    //处理右子数组
}

😜注意递归结束条件的控制😜

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

单趟排序时,我们将子数组的左端元素作为key,因此在处理有序或接近有序以及倒序或完全倒序的序列时,大多数情况下经过单趟排序后,数组的分割点(key元素的最终位置)会停留在数组左端(倒序的情况则停留在数组右端),于是整个排序过程中,数组被逐步划分过程的图示:
此时划分层次数量级为O(N),每个划分层次中单趟排序所需遍历的元素个数呈等差数列递减,此时分治递归的时间复杂度计算公式为等差数列求和式,数量级升阶为O(N^2);

为了避免这种情况出现,我们需要对key元素的选取方式进行优化

二.快速排序的优化

1.三数取中优化

优化思路:

为了避免序列有序或接近有序时,分治递归过程中不断在数组区间端点处对数组进行划分(从而导致数组划分总次数数量级为O(N)),我们采用三数取中的方式优化key的选取:

设计一个接口,确定数组的首元素,尾元素和中间位置元素三者中的中位数(中间大小的数),并返回其下标.接口首部:

int GetMid(int* arr,int left,int right)

接口实现:

int GetMid(int* arr,int left,int right)
{
	int mid = left + ((right - left) >> 2);     //在arr[left],arr[mid],arr[right]三者中取中间值作为key,返回key的下标
	if (arr[left]  arr[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (arr[left] > arr[mid] && arr[mid] > arr[right])
		{
			return mid;
		}
		else if (arr[mid] > arr[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

确定数组的首元素,尾元素和中间位置元素三者中的中位数后,将其交换到arr[left]的位置,后续的单趟排序过程我们依然选择arr[left]作为key元素

三数取中优化后的单趟排序:

int PartionV3(int* arr, int left, int right)//完成1个元素的排序,同时分割数组
{
	assert(arr);
	swap(&arr[left], &arr[GetMid(arr, left, right)]);
	int key = left;										//在arr[left],arr[mid],arr[right]三者中取中间值作为key
	int slow = left;								    //slow从left开始  
	int fast = left + 1;							    //fast从left+1开始遍历数组
	while (fast 0)					//通过元素比较确定x要插入的位置
		{
			if (x =arr[insert-1]说明insert是x要插入的位置
			}
		}					//最坏的情况下x会被插入到数组的首地址处(此时数据比较和挪动了end次)
		arr[insert] = x;    //完成元素x的插入(继续插入下一个元素)
	}
}

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

//每完成一次数组分割,就进行左右子数组分治递归完成每一个元素的排序
void QuickSort(int* arr, int left,int right)
{
	assert(arr);
	if (right - left+1  left)                //区间中有两个以上元素时,区间入栈
	{
		range.push(right);           //取的时候先取左边界,因此左边界后入栈(令左边界压在右边界上面)
		range.push(left);            //初始区间入栈;
	}
	while (!range.empty())
	{
		int left = range.top();	     //令栈顶区间出栈
		range.pop();
		int right = range.top();
		range.pop();
		
		int breakpoint = PartionV3(arr, left, right); //确定区间分割点,同时完成一个数组元素的排序
		//栈是后进先出,递归是先向左子数组递归,因此做左子数组区间后入栈
		if (right>breakpoint+1)					      //若子区间元素个数大于一个则区间入栈
		{
			range.push(right);
			range.push(breakpoint + 1);
		}
		if(breakpoint-1>left)
		{
			range.push(breakpoint - 1);
			range.push(left);
		}
	}
}