引言：

上面两篇文章讲了几种排序方法，它们的一些性能和时间复杂度我进行了总结，如果一些代码不懂可以参考《排序1》，《排序2》

1.什么是快速排序？

1.1快拍定义及图解

1.首先设定一个分界值，通过该分界值将数组分成左右两部分。 2.将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。 3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

2.hoare法实现

hoare法是快拍中比较常用的一种方法。

2.1hoare单趟实现

//快速排序单趟实现
int PartSort1(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int key = begin;
	int keyi = begin;
	if (begin >= end)//如果最多有一个就不用递归了
	{
		return;
	}
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}

		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;

2.2多趟实现

2.21大致思想：

前面我们以基准值为参考进行了简单排序，现在比基准值小的在其左边，大的在其右边。

那我们就可以分两组实现左边一组，右边一组就行了，在这里我们用递归来实现。

2.22第一种方法实现

//hoare法整体实现
void PartSort1D(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int key = begin;
	int keyi = begin;
	if (begin >= end)//如果最多有一个就不用递归了
	{
		return;
	}
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}

		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);

	keyi = left;  //把keyi交换到中间
	PartSort1D(a, begin, keyi - 1);
	PartSort1D(a, keyi + 1, end);
}

2.23第二种方法实现

这种只不过是单趟排序再加一个主函数，但是更便捷了。

int PartSort1(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int key = begin;
	int keyi = begin;
	if (begin >= end)//如果最多有一个就不用递归了
	{
		return;
	}
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
     return left;
}
//整体法
void QuickSort(int* pa, int begin, int end)
{
	assert(pa);
	if (begin >= end)
	{
		return;
	}
	//这里为单趟实现的方式
	int keyi = PartSort1(pa, begin, end);

	QuickSort(pa, begin, keyi - 1);
	QuickSort(pa, keyi + 1, end);
}

3.挖坑法实现

3.1大致思路：

以最左侧的数为基准数key,此时将key的值保存并将这个位置变成一个坑，让right左移找小于key的数，找到后将这个数要到刚才的这个坑中，right1位置又形成一个坑，再将left的值移到这个坑中，最后将key移到left，right重叠位置，重复多次。

3.2挖坑法单趟实现

//挖坑法
int PartSort2(int* a, int begin, int end)
{
	int key = a[begin];
	int tmp = begin;//坑位
	int right = end;
	int left = begin;
	while (left < right)
	{
		//当左边小于右边时循环结束
		while (left < right && a[right] >= key)
		{
			right--;
		}
		Swap(&a[tmp], &a[right]);
		tmp = right;  //把right位置变成坑位
		
		while (left < right && a[left] <= key)
		{
			left++;
		}
		Swap(&a[tmp], &a[left]);
		tmp = left;
	}
	Swap(&key, &a[tmp]);
	return  tmp;
	
}

大致思想和上面的基本一致。

3.3多趟实现第一种

思路和hoare法一模一样，以坑位tmp为界限，左边调用一次递归，右边调用一次递归就行。

//挖坑法
void PartSort2D(int* a, int begin, int end)
{
	int key = a[begin];
	int tmp = begin;//坑位
	int right = end;
	int left = begin;
	while (left < right)
	{
		//右边找小，填左坑
		while (left < right && a[right] >= key)
		{
			right--;
		}
		Swap(&a[tmp], &a[right]);
		tmp = right;
		//左边找大，填右坑
		while (left < right && a[left] <= key)
		{
			left++;
		}
		Swap(&a[tmp], &a[left]);
		tmp = left;
	}
	Swap(&key, &a[tmp]);
	PartSort2D(a, begin,tmp - 1);
	PartSort2D(a, tmp + 1, end);
}

3.4第二种方法实现

//挖坑法
int PartSort2(int* a, int begin, int end)
{
	int key = a[begin];
	int tmp = begin;//坑位
	int right = end;
	int left = begin;
	while (left < right)
	{
		//当左边小于右边时循环结束
		while (left < right && a[right] >= key)
		{
			right--;
		}
		Swap(&a[tmp], &a[right]);
		tmp = right;  //把right位置变成坑位
		
		while (left < right && a[left] <= key)
		{
			left++;
		}
		Swap(&a[tmp], &a[left]);
		tmp = left;
	}
	Swap(&key, &a[tmp]);
	return  tmp;
	
}
//整体法
void QuickSort(int* a, int begin, int end)
{
	assert(a);
	if (begin >= end)
	{
		return;
	}
	//这里为单趟实现的方式
	int keyi = PartSort2(a, begin, end);

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

这里就不过多解释了。

4.前后指针法

4.1前后指针思路分析

一个先行指针cur,一个后行prev,cur先走，当遇见小于key的值时，两者同步，当遇见大于key的值时，cur继续往前走，prev不动，所以prev前面一定是大于key的数，直到cur找到小于key的值时停下，然后交换cur和prev前面那个数.

4.11那能不能进行单趟实现呢？

可以，当cur遇见的都是小于key的值时，prev,cur同步，当cur出界限时，prev和key完成交换，单趟结束。

4.2源码单趟实现

//前后指针法
int PartSort3(int* a, int begin, int end)
{
	int key = begin;
	int cur = begin + 1;
	int prev = begin;
	while (cur <= end)
	{
		if ((a[cur] < a[key]) && (++prev != cur))
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[key]);
	return prev;
	
}

4.3多趟实现

//前后指针法
void PartSort3D(int* a, int begin, int end)
{
	int key = begin;
	int cur = begin + 1;
	int prev = begin;
	while (cur <= end)
	{
		if ((a[cur] < a[key]) && (++prev != cur))
           //交换prev的前一个值
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[key]);
	
	QuickSort(a, begin, prev - 1);
	QuickSort(a, key + 1, end);
}

非递归实现下次在更新吧。

数据结构------排序3（快速排序）

引言：