排序算法：快速排序(递归)

所属专栏:C++初阶
引言：这里所说的快速排序有三种，第一种是霍尔大佬自创的，还有一种叫做挖坑法，另外一种叫前后指针法

一、创始人托尼·霍尔的快速排序

1.这里我们先把中间值定位数组中的首元素的值，设为key变量，大于key的放右边，小于key的放左边
2.定义left为从数组0下标开始找大于key的数，如果小于key，left就向前走一步，定义right从数组下标为n-1的位置，从右向左找小于key的数，从最右边的数开始，如果大于key，right就向后走一步
3.这里我们还要判断谁先和谁相遇（也就是谁走到相等的位置，而那个人是停止的)
如果left先走，那么left与right相遇的地方就是left走遇到right(相遇的地方的值是大于key的)
如果right先走，那么left与right相遇的地方就是right走遇到left(相遇的地方的值是小于key的)

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* p1,int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
int QuickSort(int left,int right,int* a)
{int keyi = left;int end = right;//判断谁先走的问题，我们把大于a[keyi]的放左边//小于a[keyi]的放右边，等于的话就不管//这里要判断谁先走的问题//如果left先走，那么left与right相遇的地方就是left走遇到right//如果right先走，那么left与right相遇的地方就是right走遇到leftwhile (left < right){//右边找小while(left < right && a[right] >= a[keyi])right--;//左边找大while(left < right && a[left] <= a[keyi])left++;Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}void TestSort(int* a, int begin,int end)
{if (begin >= end)//当只有一个数时，不用排序，直接返回return;//霍尔大佬的排序int keyi = QuickSort(begin, end ,a);TestSort(a, begin,keyi-1);TestSort(a, keyi+1,end);
}
int main()
{int a[] = {6,1,2,7,9,3,4,5,10,8};TestSort(a, 0, sizeof(a) / sizeof(int) - 1);for (int i = 0; i < sizeof(a) / sizeof(int); i++)printf("%d ", a[i]);return 0;
}

这里的排序就像是二叉树的遍历，大家可以参考前面的代码
排序区间【begin，keyi-1】keyi 【keyi+1,end】（keyi为中间值，已经排好序了）

二、挖坑法

步骤如下：
1.这里的挖坑（从a[left]开始是第一个坑，然后right寻找小于key（a[left]）的值，找到了这个坑就跑到a[right]去了，同时要交换一下下标hole=right）
2.然后就从left开始找大于key的值，找到了那么就是第二个坑，hole就跳到了left的位置，hole=left
3.以此类推，直到left=right的时候，此时的坑就在left=right的地方，然后a[hole]=key（此时的key就是中间值不需要排了）

int QuickSort(int left,int right,int* a)
{int key = a[left];int end = right;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 left;
}

三、前后指针法

步骤如下：
1.首先定义一个前指针prev，和一个后指针cur
2.然后cur先向前走，如果大于key，那么继续向前走，prev，不向前走，如果小于key，那么prev和cur同时向前走（总的来说cur一直是向前走的，prev只在cur位置小于key才向前走的）
3.以此类推，直到cur>end就不走了

int QuickSort3(int left, int right, int* a)
{int key = a[left];int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] <= key && ++prev != cur)Swap(&a[prev],&a[cur]);cur++;}//最后这里的a[prev]一定是一个小于key的值，//所以需要和key这个中间值换一下，以达到key已经排好序Swap(&a[prev], &a[left]);return prev;
}