带你详细了解交换排序之快速排序

1.快速排序的由来

快速排序是Hoare于1962年提出的一种二叉树结构的交换顺序的方法，其基本思想为：

任取待排序元素序列中的某元素为基准值，按照该基准值将待排序集合分割成两个子序列：左子序列中所有的元素均小于基准值，右子序列中所有的元素均大于基准值。然后左右子序列重复该过程，直到所有元素都排列在相应的位置上为止。

当为单个元素的时候，就代表操作完成。

2.快速排序的三种方法

2.1 Hoare法

Hoare排序实现思路：

就可以实现Hoare的快速排序啦

可以参照代码进行理解：

//Hoare法排序
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		while (left=a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
 
		Swap(&a[left], &a[right]);
	}Swap(&a[keyi], &a[left]);
	return left;//keyi的值最后会被交换到a[left]的位置
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
 
}

2.1.1 Hoare疑惑讲解

Hoare法排序是这个三种方法坑最多的方法，所以下面详细解答一下疑惑：

（1）while的大条件为 left < right 为什么里面的while的小条件还要包括 left < right ？

大条件的 left < right : 固定寻找下标的范围，找到满足条件的，进行Swap交换

小条件的 left < right : 其一，是防止a[left] or a[right]越界访问

                                     其二，是预防已经交换的值再次会进行交换，破坏顺序

（2）为什么返回值为left，而不是keyi ?

在最后，key会被与a[left]交换，所以要返回值为key的left

（3）在QuickSort函数里为什么会加上 if(begin>= end) 而不是 if(begin == enf) ?

首先，我们要分别了解一下 单元素返回 和 空元素返回 ：

单元素返回：begin == end

空元素返回： begin > end

（4）在这里面 keyi 的位置为什么要从left开始，而不是right ？

其实左右都可以作为keyi：

1.左边做 keyi,右边先走；保障相遇位置的值比key小 or 就是keyi的位置

L和R相遇，无非就是两种情况：

L遇到R;

R遇到L

L遇到R：R是停下来，L在走。R先走，R停下来的位置的值一定比keyi的值小，相遇的位置就是R停下来的位置，所以该位置的值一定比keyi小

R遇到L: 再相遇的这一轮，L就没动，R在移动，跟L相遇，相遇的位置就是L的位置，L的位置就是keyi的位置 or 交换过一次轮次，相遇L的位置的值一定比keyi的值要小

2.右边做 keyi,左边先走；保障相遇位置的值比key大 or 就是keyi的位置

原理大致相同

（5）时间复杂度为多少？

最优条件下，可以达到：O（nlogn）

最坏条件，可以达到：O（n^2）

2.2 挖坑法

挖坑法其实和Hoare法差不多，就是交换的方法有所差异，挖洞法的交换更容易理解：

也可以看一下动图，更方便理解：

基本跟Hoare法排序一样，限制条件也一样，代码如下：

//挖洞法排序
int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
 
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

2.3跟屁虫法

基本实现如下图动图所示：

相比之前的两种方法，这个更为直接明了，方便理解和编写代码。

代码如下：

//跟屁虫法
int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur<=right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	
	Swap(&a[keyi], &a[prev]);
	return prev;
}

3.总结

多多结合代码看看动图的实现，在下一篇会对快速排序进行优化~~

加油，与君共勉！！