回顾快速排序

快速排序

快速排序的核心：

找到一个key

通常左边的数比key小，右边的数比key大。

找key通常有三种方法：

1.

挖坑法：

代码实现：

//
int _pivot(int* a, int left, int right)
{
	int begin = left, end = right;
	int index = get_mid(a, left, right);
	swap(a[index], a[begin]);
	int key = a[begin];
	int pivot = begin;
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		//swap(a[end], a[pivot]);
		a[pivot] = a[end];
		pivot = end;
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		//swap(a[begin], a[pivot]);
		a[pivot] = a[begin];
		pivot = begin;
	}
	//swap(a[begin], a[pivot]);
	pivot = begin;
	a[pivot] = key;
	return pivot;
}

 该代码的注意点为：

如果a[begin]或a[end]与key相等时，key原来在key的那边，while循环后key还在原来那边。

swap交换是错误的例子。

pivot是坑，a[pivot]是图里面类似于马赛克的位置（a[pivot]是空）,所以不能是交换，应该是赋值。

左右指针法：（最左侧的一列是其示例图）

 图中代码有本质差别，图一正确（左）。

 先end--

后end--

二者有质的区别，完全不同

前后指针法：

找到key之后的核心：