快速排序的优化思路

大忽悠爱学习

发布于 2021-11-15 10:17:44

4530

在对快速排序进行优化前，先让我们回顾一些快速排序的思想： 快速排序就是分而治之思想的体现，将有序序列分成对立的两部分，一部分值都比关键字值小，一部分值都比关键字值大，再分别对两部分进行排序对快速排序不了解的可以先看看快速排序的具体过程和代码讲解 下面来看代码：

#include<iostream>
#include<algorithm>
using namespace std;
//该函数作用：把比关键字小的放到关键字的左边，比关键字大的放到关键字右边
int partition(int arr[],int len,int low,int high)
{
	int pivotkey;
	//用数组的第一个元素做关键值
	pivotkey = arr[low];
	//从数组两端交替向中间扫描
	while (low < high)
	{
		//先从数组末端开始往前找到一个比关键值小的值，放到关键值右边
		while (low < high && pivotkey < arr[high])
			high--;
		//交换后，关键值移动到high都位置
		swap(arr[high],arr[low]);
		//从数组起点开始往后端移动，直到找到一个比关键字大的元素，放到关键字左边
		while (low<high && pivotkey>arr[low])
			low++;
		//交换后，关键值移动到low的位置
		swap(arr[low], arr[high]);
	}
	//最后low=high,都指向最后关键值的下标位置
	return low;
}
void Qsort(int arr[], int len,int low,int high)
{
	int pivot;//记录关键值的位置
	if (low < high)
	{
		//获取当前关键值的位置（在数组中的下标）
		pivot=partition(arr, len, low, high);
		//分别对关键值前面较小部分和后面较大部分进行排序
		Qsort(arr, len, low, pivot - 1);
		Qsort(arr, len, pivot + 1, high);
	}
}
void QuickSort(int arr[],int len)
{
	Qsort(arr, len,0,len-1);
}
void test()
{
	int arr[9] = { 50,10,90,30,70,40,80,60,20 };
	QuickSort(arr, 9);
	for (int i = 0; i < 9; i++)
		cout << arr[i] << " ";
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}

快速排序优化

1.优化选取枢轴 （1）三数取中法取三个关键字进行排序，将中间数作为关键值，一般是取左端，右端和中间三个数，也可以随机选取我们只需要在partition函数增加这样一段代码：

//该函数作用：把比关键字小的放到关键字的左边，比关键字大的放到关键字右边
int partition(int arr[],int len,int low,int high)
{
	int pivotkey;
	//优化关键值选择
	int m = low + (high - low) / 2;//计算数组中间元素的下标
	if (arr[low] > arr[high])
		swap(arr[low], arr[high]);//交换左端与右段数据，保证左端较小
	if(arr[m]>arr[high])
		swap(arr[m], arr[high]);//交换右端与中间数据，保证中间较小
	if (arr[m]>arr[low])
		swap(arr[m], arr[low]);//交换low位置为整个序列左中右三个关键字的中间值
	pivotkey = arr[low];
	//从数组两端交替向中间扫描
	while (low < high)
	{
		//先从数组末端开始往前找到一个比关键值小的值，放到关键值右边
		while (low < high && pivotkey < arr[high])
			high--;
		//交换后，关键值移动到high都位置
		swap(arr[high],arr[low]);
		//从数组起点开始往后端移动，直到找到一个比关键字大的元素，放到关键字左边
		while (low<high && pivotkey>arr[low])
			low++;
		//交换后，关键值移动到low的位置
		swap(arr[low], arr[high]);
	}
	//最后low=high,指向最后关键值的下标位置
	cout << "low= "<<low << "high= "<<high << endl;
	return low;
}

还有个办法就是所谓的九数取中法，它先从数组中分三次取样，每一次取三个数，三个样品各取出中数，然后从这三个中数中再取出一个中数作为关键值 2.优化不必要的交换 将关键字用一个临时值保存下来，省去之前每一次都要把关键字和别的元素交换位置的过程，等最后找到中枢的位置，再将关键字填入

//该函数作用：把比关键字小的放到关键字的左边，比关键字大的放到关键字右边
int partition(int arr[],int len,int low,int high)
{
	int pivotkey;
	//优化关键值选择
	int m = low + (high - low) / 2;//计算数组中间元素的下标
	if (arr[low] > arr[high])
		swap(arr[low], arr[high]);//交换左端与右段数据，保证左端较小
	if(arr[m]>arr[high])
		swap(arr[m], arr[high]);//交换右端与中间数据，保证中间较小
	if (arr[m]>arr[low])
		swap(arr[m], arr[low]);//交换low位置为整个序列左中右三个关键字的中间值
	pivotkey = arr[low];
	//从数组两端交替向中间扫描
	while (low < high)
	{
		//先从数组末端开始往前找到一个比关键值小的值，放到关键值右边
		while (low < high && pivotkey < arr[high])
			high--;
		//这里实现的是假交换操作
		arr[low] = arr[high];
		//从数组起点开始往后端移动，直到找到一个比关键字大的元素，放到关键字左边
		while (low<high && pivotkey>arr[low])
			low++;
		//假交换，真替换
		arr[high] = arr[low];
	}
	cout << "low=" << low << "  high=" << high << endl;
	arr[low] = pivotkey;
	return low;
}

3.优化小数组的排序方案 如果数组非常小，其实快速排序不如直接插入排序来得更好（直接插入排序是简单排序中性能最好的）因为快速排序需要用到递归操作，对于大量数据操作时，这点性能影响对于它的整体算法优势而言可以忽略不计，但如果数组只有几个数据需要排序的时候，这就成了一个大炮打蚊子的大问题，我们需要改进一些Qsort函数

#define MAX_LENGHT_INSERT_SORT 7  //数组长度阈值
void Qsort(int arr[], int len,int low,int high)
{
	int pivot;//记录关键值的位置
	if ((high-low+1)> MAX_LENGHT_INSERT_SORT)//当high-low大于常数时用快速排序
	{
		//获取当前关键值的位置（在数组中的下标）
		pivot=partition(arr, len, low, high);
		//分别对关键值前面较小部分和后面较大部分进行排序
		Qsort(arr, len, low, pivot - 1);
		Qsort(arr, len, pivot + 1, high);
	}
	else//当high-low小于等于常数时用直接插入排序
	{
		//当某一部分子序列长度小于常数时，就用直接插入排序进行排序操作
		InsertSort(arr,high,low);
	}
}

有资料认为7比较合适，也有认为50比较合适，实际应用可做适当调整 4.优化递归操作 QSort函数在其尾部有两次递归操作，如果能减少递归，将会大大提高性能，于是我们对QSort实施尾递归操作

#define MAX_LENGHT_INSERT_SORT 7  //数组长度阈值
void Qsort(int arr[], int len,int low,int high)
{
	int pivot;//记录关键值的位置
	if ((high-low+1)> MAX_LENGHT_INSERT_SORT)//当high-low大于常数时用快速排序
	{
		//获取当前关键值的位置（在数组中的下标）
		pivot=partition(arr, len, low, high);
		//分别对关键值前面较小部分和后面较大部分进行排序
		Qsort(arr, len, low, pivot - 1);
		//尾递归
		low = pivot + 1;
	}
	else//当high-low小于等于常数时用直接插入排序
	{
		//当某一部分子序列长度小于常数时，就用直接插入排序进行排序操作
		InsertSort(arr,high,low);
	}
}

但我们把if改成while以后，因为第一次递归后，变量low就没有用处了，所以可以将pivot+1赋值给low,再循环一次，来一次Partition(arr,low,high)，其效果等同于QSort(arr,pivot,high)。结果相同，但因为采用迭代而不是递归的方法可以缩减堆栈的深度，从而提高整体性能 优化后的完整代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
//该函数作用：把比关键字小的放到关键字的左边，比关键字大的放到关键字右边
int partition(int arr[],int len,int low,int high)
{
	int pivotkey;
	//优化关键值选择
	int m = low + (high - low) / 2;//计算数组中间元素的下标
	if (arr[low] > arr[high])
		swap(arr[low], arr[high]);//交换左端与右段数据，保证左端较小
	if(arr[m]>arr[high])
		swap(arr[m], arr[high]);//交换右端与中间数据，保证中间较小
	if (arr[m]>arr[low])
		swap(arr[m], arr[low]);//交换low位置为整个序列左中右三个关键字的中间值
	pivotkey = arr[low];
	//从数组两端交替向中间扫描
	while (low < high)
	{
		//先从数组末端开始往前找到一个比关键值小的值，放到关键值右边
		while (low < high && pivotkey < arr[high])
			high--;
		//这里实现的是假交换操作
		arr[low] = arr[high];
		//从数组起点开始往后端移动，直到找到一个比关键字大的元素，放到关键字左边
		while (low<high && pivotkey>arr[low])
			low++;
		//假交换，真替换
		arr[high] = arr[low];
	}
	arr[low] = pivotkey;
	return low;
}
void InsertSort(int arr[],int high,int low)
{
	int j;
	for (int i = low+1; i <= high; i++)
	{
		if (arr[i] < arr[i - 1])
		{
			int temp = arr[i];
			for (j = i - 1; temp<arr[j]&&j>=low; j--)
			{
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp;
		}
	}
}
#define MAX_LENGHT_INSERT_SORT 7  //数组长度阈值
void Qsort(int arr[], int len,int low,int high)
{
	int pivot;//记录关键值的位置
	if ((high-low+1)> MAX_LENGHT_INSERT_SORT)//当high-low大于常数时用快速排序
	{
		while (low < high)
		{
			//获取当前关键值的位置（在数组中的下标）
			pivot = partition(arr, len, low, high);
			//分别对关键值前面较小部分和后面较大部分进行排序
			Qsort(arr, len, low, pivot - 1);
			//尾递归：因为这里把if语句巧妙变成了while语句
			//所以这里low=关键值下标+1，得到的就是另一半大的部分的起点，然后直接再次进入while循环，再获取大的部分的关键值位置
			low = pivot + 1;
		}
	}
	else//当high-low小于等于常数时用直接插入排序
	{
		//当某一部分子序列长度小于常数时，就用直接插入排序进行排序操作
		InsertSort(arr,high,low);
	}
}
//升序
void QuickSort(int arr[],int len)
{
	Qsort(arr, len,0,len-1);
}
void test()
{
	int arr[8] = { 50,10,30,70,40,80,60,20 };
	QuickSort(arr, 8);
	for (int i = 0; i < 8; i++)
		cout << arr[i] << " ";
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/04/10 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度