【排序算法】快速排序（可视化描述，三种方法实现，四种方法优化）

2018-07-29

写在前面

这篇文章通过动态图的描述详细介绍了快速排序的原理与过程。
代码实现用三种思想完成（分治思想）。
文章中包含了四种优化方式以及实现原理（包括多线程优化）。

这里写图片描述

该方法的基本思想是：

(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”；

(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大；

(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

总结起来就是：挖坑思想 + 分治思想

对于分治思想，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。

最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列。

方法一：

第一种方法就是直接选择这个数组的第一个元素或者最后一个元素作为基准进行排序。这种方法也是基本的快排做法，存在效率问题。

int SelectPivot(int arr[],int low,int high)
//low第一个元素，high最后一个元素
{
	return arr[low];//选择选取序列的第一个元素作为基准
}

如果这个数组有序，那么每次只能使这个序列 -1，就会沦为冒泡排序，时间复杂度变成O(N^2)。

方法二：

随机选择一个基准。

/*随机选择枢轴的位置，区间在low和high之间*/
int SelectPivotRandom(int arr[],int low,int high)
{
	//产生基准的位置
	srand((unsigned)time(NULL));
	int pivotPos = rand()%(high - low) + low;

	//把基准位置的元素和low位置元素互换，此时可以和普通的快排一样调用划分函数
	swap(arr[pivotPos],arr[low]);
	return arr[low];
}

由于基准的位置是随机的，那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时，仍然是最坏情况，时间复杂度是O(n^2）。

但是数据相等的概率比较小，所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn）的期望时间复杂度。“随机化快速排序可以满足一个人一辈子的人品需求”。

方法三：

三数取中：效率最高的情况就是这个基准能将数组序列划分成等长度的两部分，但是这个数很难找出来，还容易拖慢快排速度。

这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准。

给定待排序序列为：8 1 4 9 6 3 5 2 7 0

左边为：8，右边为0，中间为6。

三个数排序后，中间那个数作为基准，则基准为6。

具体思想：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为基准，并用0下标元素存储该基准。

/*函数作用：取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴*/
int SelectPivotMedianOfThree(int arr[],int low,int high)
     //三数取中
{
	int mid = low + ((high - low) >> 1);//计算数组中间的元素的下标

	//使用三数取中法选择枢轴
	if (arr[mid] > arr[high]) //目标: arr[mid] <= arr[high]
	{
		swap(arr[mid],arr[high]);
	}
	if (arr[low] > arr[high]) //目标: arr[low] <= arr[high]
	{
		swap(arr[low],arr[high]);
	}
	if (arr[mid] > arr[low]) //目标: arr[low] >= arr[mid]
	{
		swap(arr[mid],arr[low]);
	}
	//此时，arr[mid] <= arr[low] <= arr[high]
	return arr[low];
	//low的位置上保存这三个位置中间的值
	//分割时可以直接使用low位置的元素作为基准，而不用改变分割函数了
}

性能测试方法：

1、随机生成100万个数据对函数进行性能测试；

2、生成100万个相等数据，测试函数性能；

3、生成100万个有序数据，测试函数性能。

优化一：

对于很小或者部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排。

截止范围：待排序序列长度N = 10，（在5 - 20之间可能都会存在这样的效率问题）

if (high - low + 1 < 10)
{
	InsertSort(arr,low,high);
	return;
}//else时，正常执行快排

优化二：

在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割。

待排序序列 1 4 6 7 6 6 7 6 8 6

三数取中选取基准：基准key = 6

本次划分后，未对与key元素相等处理的结果：1 4 6 6 7 6 7 6 8 6

下次的两个子序列为：1 4 6 和 7 6 7 6 8 6

本次划分后，对与key元素相等处理的结果：1 4 6 6 6 6 6 7 8 7

下次的两个子序列为：1 4 和 7 8 7

在一次划分后，把与key相等的元素聚在一起，能减少迭代次数，效率会提高不少。

具体思想：

第一步，在划分过程中，把与key相等元素放入数组的两端

第二步，划分结束后，把与key相等的元素移到枢轴周围

变态代码：

void QSort(int arr[],int low,int high)
{
	int first = low;
	int last = high;

	int left = low;
	int right = high;

	int leftLen = 0;
	int rightLen = 0;

	if (high - low + 1 < 10)
	{
		InsertSort(arr,low,high);
		return;
	}

	//一次分割
	int key = SelectPivotMedianOfThree(arr,low,high);//使用三数取中法选择基准

	while(low < high)
	{
		while(high > low && arr[high] >= key)
		{
			if (arr[high] == key)//处理相等元素
			{
				swap(arr[right],arr[high]);
				right--;
				rightLen++;
			}
			high--;
		}

		arr[low] = arr[high];
		while(high > low && arr[low] <= key)
		{
			if (arr[low] == key)
			{
				swap(arr[left],arr[low]);
				left++;
				leftLen++;
			}
			low++;
		}
		arr[high] = arr[low];
	}
	arr[low] = key;

	//一次快排结束
	//把与枢轴key相同的元素移到枢轴最终位置周围
	int i = low - 1;
	int j = first;
	while(j < left && arr[i] != key)
	{
		swap(arr[i],arr[j]);
		i--;
		j++;
	}
	i = low + 1;
	j = last;
	while(j > right && arr[i] != key)
	{
		swap(arr[i],arr[j]);
		i++;
		j--;
	}
	QSort(arr,first,low - 1 - leftLen);
	QSort(arr,low + 1 + rightLen,last);
}

这是一个性能测试分析图：（大神的）

测试数据分析：三数取中选择枢轴+插排+聚集相等元素的组合，效果竟然好的出奇。其实这里，插排的作用还是不怎么大的。

优化三：

快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化。

优点：如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。

void QSort(int arr[],int low,int high)
{
	int pivotPos = -1;
	if (high - low + 1 < 10)
	{
		InsertSort(arr,low,high);
		return;
	}
	while(low < high)
	{
		pivotPos = Partition(arr,low,high);
		QSort(arr,low,pivotPos-1);
		low = pivotPos + 1;
	}
}

/////注意：在第一次递归后，low就没用了，此时第二次递归可以使用循环代替/////