其实就是对快速排序的优化。

---

一、挖坑法

        这种方法其主要是好理解，其快排的本质却没有改变。

        其主要思路是，把key对应位置空出来，然后两边同样找大找小，只不过这次把找到的数，放到空位置处。

        找到最后左边和右边相遇，此时相遇的位置必定为坑，再把key放过来就好。

        这样一次排序就完成了。如果其左边有坑，天然要从右边开始找。如果key找的是右边，其天然要从左边开始找。

        这种找法跟传统的排序其本质差不多，但是要注意其数据移动的位置的不同于传统快排的。如果有选择题是，快排的移动顺序的题目，要考虑到这个点。

//挖坑法
int PostSort(int* arr, int begin, int end)
{
	int key = arr[begin];
	int piti = begin;
 
	while (begin<end)
	{
		while (begin<end && arr[end]>=key) {
			end--;
 
		}
 
		arr[piti] = arr[end];
		piti = end;
 
		while (begin<end && arr[begin]<=key)
		{
			begin++;
		}
 
		arr[piti] = arr[begin];
		piti = begin;
 
	}
 
	arr[piti] = key;
 
	return piti;
 
}
 
void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end) {
		return;
	}
 
	int pos = PostSort(arr,begin,end);
 
	QuickSort(arr, begin, pos - 1);
 
	QuickSort(arr, pos + 1, end);
}

二、前后指针法

        定义两个指针，cur往前走，遇到数据小于 key 则 pre 往前走一步。cur遇到比key大的，自己往前走，pre不动。

        直到遇到下一个比key小的数，pre往前走一步，然后交换数据。

         

        

        cur遇到比key大的数据后，两个指针就拉开了距离。

 

         继续重复上面的步骤，直到cur到头后，交换key和pre位置的数据。

 

代码：

//前后指针法
int PostSort2(int* arr, int begin, int end)
{
 
	int cur = begin + 1;
	int pre = begin;
	int key = arr[begin];
 
	while(cur <= end) {
		
		if (arr[cur]<key && ++pre!=cur) {
 
			swap(&arr[pre], &arr[cur]);
 
		}
 
		cur++;
	
	}
 
	swap(&arr[pre],&arr[begin]);
 
	return pre;
 
}
 
 
 
void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end) {
		return;
	}
 
	int pos = PostSort2(arr, begin, end);
 
	QuickSort(arr, begin, pos - 1);
 
	QuickSort(arr, pos + 1, end);
}

三、 快排速度优化

        注意，理解了快速排序的原理，那么就知道，如果key找到后的位置，一直是中位数，那么其数组区间二分 logN。递归下去每一层的时间复杂度为 N。

        所以得，其快速排序时间复杂度最快的情况为 N*logN。

        如果key选择的是最小或者最大，那么其为最坏的情况。而如果数组有序（或者接近有序），那么其选择的key一定为最小或最大。

        其时间复杂度为一个等差数列，所以得出，快速排序在有序或者接近有序的情况下，时间复杂度为O(N^2)。

PS：而且这里递归太深会造成，栈溢出。

1、三数取中

        取开始 中间 结尾，选不是最大，也不是最小那个。强行把数组变为二分，提高运行效率。

//三数取中
int GetMidIndex(int* arr, int begin, int end)
{
	int mid = (begin + end) / 2;
 
	if (arr[begin] < arr[mid]) {
 
		if (arr[mid] < arr[end])
		{
			return mid;
		}
		else if (arr[end] < arr[begin])
		{
			return begin;
		}
		else  //arr[begin] < arr[end]
        { 
			return end;
		}
 
	}
	else {    // arr[begin] > arr[mid]
		if (arr[mid] > arr[end])
		{
			return mid;
		}
		else if (arr[begin] > arr[end])
		{
			return end;
		}
		else   //arr[begin]<arr[end]
		{   
			return begin;
		}
	}
}
 
//前后指针法
int PostSort2(int* arr, int begin, int end)
{
 
	int cur = begin + 1;
	int pre = begin;
	int key = begin;
	int mid = GetMidIndex(arr, begin, end);
 
	swap(&arr[key],&arr[mid]);
 
	while(cur <= end) {
		
		if (arr[cur]<arr[key] && ++pre != cur) {
			swap(&arr[pre], &arr[cur]);
		}
 
		cur++;
	
	}
	swap(&arr[pre],&arr[begin]);
 
	return pre;
 
}
 
 
void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end) {
		return;
	}
	
 
	int pos = PostSort2(arr, begin, end);
 
	QuickSort(arr, begin, pos - 1);
 
	QuickSort(arr, pos + 1, end);
}

2、小区间优化

        假设一个数组进行快速排序，其递归图入下。

         这里可以发现，部分小区间，其实就没必要再使用快速排序，这里可以使用其他排序来代替。

PS：这里把最后一层优化掉，就相当于去掉了50%的调用。

//前后指针法
int PostSort2(int* arr, int begin, int end)
{
 
	int cur = begin + 1;
	int pre = begin;
	int key = begin;
 
	int mid = GetMidIndex(arr, begin, end);
 
	swap(&arr[key],&arr[mid]);
 
	while(cur <= end) {
		
		if (arr[cur]<arr[key] && ++pre != cur) {
			swap(&arr[pre], &arr[cur]);
		}
 
		cur++;
	
	}
	swap(&arr[pre],&arr[begin]);
 
	return pre;
 
}
 
 
 
// 插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n; i++) {
		int end = i;
		int temp = a[end + 1];
 
		while (end >= 0)
		{
			if (temp < a[end]) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				break;
			}
			a[end + 1] = temp;
		}
	}
}
 
 
//小区间优化
void QuickSort_2(int* arr, int begin, int end)
{
	if (begin >= end) {
		return;
	}
 
	if (end - begin > 2) { //区间小于 2 ，就使用插入排序
		
		
		int pos = PostSort2(arr, begin, end);
 
		QuickSort(arr, begin, pos - 1);
 
		QuickSort(arr, pos + 1, end);
 
	}
	else {
 
		//插入排序
		InsertSort(arr + begin, end - begin + 1 ); //
	} 
 
}

3、递归改非递归

        如果递归深处太深，那么会出现栈溢出。那么这里可以使用数据结构——栈来模拟递归的结构。因为这里栈的数据都在堆上生成的，堆的空间很大，所以可以进行深层次的调用。

 

        首先为了对应其递归的顺序，这里先把right入栈，这样出来先使用的就是left。

        再这个区间内排序完成后呢，再次把以key为分割的两个区间，再入栈。

         然后再进行排序，不过这里要注意，这里key-1到 left 的区间要全部排完后，才会轮到key+1到 right 区间排序。

        会发现这里就跟递归非常相似了（跟二叉树的前序遍历也非常像）。

代码：

//前后指针法
int PostSort2(int* arr, int begin, int end)
{
 
	int cur = begin + 1;
	int pre = begin;
	int key = begin;
 
	int mid = GetMidIndex(arr, begin, end);
 
	swap(&arr[key],&arr[mid]);
 
	while(cur <= end) {
		
		if (arr[cur]<arr[key] && ++pre != cur) {
			swap(&arr[pre], &arr[cur]);
		}
 
		cur++;
	
	}
 
	swap(&arr[pre],&arr[begin]);
 
    return pre;
}
 
 
//快速排序 递归改非递归
void QuickSortNonR(int* arr, int begin, int end)
{
	stack St;
	StackInit(&St);
 
	StackPush(&St,end);
	StackPush(&St,begin);
 
	while (!StackIsEmpty(&St))
	{
		int left = StackTop(&St);
		StackPop(&St);
 
		int right = StackTop(&St);
		StackPop(&St);
 
		int key = PostSort2(arr,left,right);
		
		if (right > key + 1) {
 
			StackPush(&St, right);
			StackPush(&St, key + 1);
		}
 
        if (left < key - 1) {
			
			StackPush(&St, key-1);
			StackPush(&St, left);
		}
 
	}
    
    StackDestory(&St);
}

测试：

 

拓展思路：

        使用队列来模拟递归，实现快速排序。其与用栈模拟的方式，单趟排序的顺序不一样。

        这里先把 left 和 right 入列，在此区间内进行排序。

        排序完成后把以key分割的两个区间入列。

        这里前一个区间排序完成后，把它下一个区间入列。

         再下一次取出的区间是6 到 9 ，会发现跟前面的二叉树的层序遍历相似。

         虽然其排序的顺序跟递归的方式不同，但是其每个区间相互不影响，所以其结果是相同的，效果一样。

---