隶属于交换排序思想的快速排序，时间复杂度很顶。O(N*logN)
先说一下分类和整体思路，不然容易写迷糊了。 整个逻辑，先看下图！！！
先完成单趟排序 - 搞一个数
1、hoare创始人版本
2、挖坑法
3、前后指针法 - 代码精简，逻辑严密
快排的单趟排序（一）hoare
思想：
1、选一个关键字key，一般是可以是最左边的，也可以是最右边的
2、单趟排序以后的目标是：左边的值比key值小，右边的值比key大
3、此时key就是所落到的位置，不需要再动了，将数组分为左区间和右区间，整个数组就有序了。
????????相遇位置：
????????最后相遇位置，这个值和key交换。
????????为了保证相遇位置的值，满足交换之后，左边区间都是小于key，右边区间都是大于key。
????????条件：
????????选择最左边的值做key，右边先走，左右相遇时比key小。
????????选择最右边的值做key，左边先走，左右相遇时比key大。
?
?
int Partion(int* a, int left, int right)
{
int keyi = left;
while (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[keyi], &a[left]);
return left;
}快排的单趟排序（二）- 挖坑法
思想：
右边找小，放在左边的坑中，自己为坑
左边找大，放在右边的坑中，自己为坑
最后把key放进坑中。
int Partion2(int* a, int left, int right)
{
int key = a[left];
int pivot = left;
while (left < right)
{
//右边找小，放在左边的坑中
while (left < right && a[right] >= key)
{
--right;
}
a[pivot] = a[right];
pivot = right;
//左边找大，放在右边的坑中
while (left < right && a[left] <= key)
{
++left;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
?快排的单趟排序（三）- 前后指针法
逻辑控制严密，首推
主要控制的思想就是 prev要么紧跟着cur，两者自己换自己，无所谓
要么prev紧跟着比key大的序列，将小的和大的换一下，达到左边是小的，右边是大的目的
?注意左右两边做key，最后交换key和prev是不同的位置交换，建议画图理解。
int Partion3(int* a, int left, int right)
{
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}第二步，完成整体排序 - 快排整个过程
快排的递归实现
可以借鉴二叉树的思想
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = Partion(a, left, right);
//区间[0,keyi-1], keyi - 相遇位置，就分左右区间, [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}递归都知道，有缺陷，
递归程序缺陷：
1、相比循环，性能差。（建立栈帧，早期优化不好，现在编译器优化很好，性能差不多）
2、核心问题，递归深度太深，导致栈溢出（或者没写循环条件 （属实自己问题））
尤其是递归到最后几层的时候，每个区间数据很少，区间到时很多，影响快排效率，那么我们在最后几层的时候不调用递归排序了，使用一种小区间优化的思想。不用递归，用啥呢？
直接插入排序，选择排序，冒泡排序进行横向对比：
选择排序是最坏的排序算法，不管什么场景都是O(N^2)
直接插入和冒泡排序，最坏都是O(N^2),最好都是O(N)。
已经有序的数组，两者都一样好，对接近有序的数组，是直接插入最好。
小区间优化的快排
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
//小区间优化，当分割为小区间时候，不使用递归排序
//直接插入排序，减少递归排序次数
if (right - left + 1 < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
int keyi = Partion3(a, left, right);
//区间[0,keyi-1], keyi - 相遇位置，就分左右区间, [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}快排的缺陷，影响快排这个称号：
?
如何解决快排有序选key的问题？
1、随机选key。
2、三数去中 - 左边、右边、中间，去值为中间的数作为key。面对有序的情况，就能处理成最好情况。
int GetMidIndex(int* a, int left, int right)
{
//int mid = (left + right) / 2;
int mid = left + ((right - left) >> 1);
if (a[left] < a[mid])
{
if (a[mid] < a[right])
return mid;
else if (a[left] > a[right])
return left;
else
return right;
}
else
{
if (a[mid] > a[right])
return mid;
else if (a[left] < a[right])
return left;
else
return right;
}
}
// 快速排序递归实现
// 快速排序hoare版本
int Partion(int* a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
int keyi = left;好了，这下快排缺陷解决了，但是很烦人，递归这个东西能不调用就不调用，栈会溢出，所以还需要一个非递归实现
快排的非递归实现
递归深度太深会导致栈溢出，所以使用非递归实现快排。主要思想就是，使用栈的思想代替递归时栈针的保存值。
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
ST st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
int end = StackTop(&st);
StackPop(&st);
int begin= StackTop(&st);
StackPop(&st);
int keyi = Partion3(a, begin, end);
//[begin, keyi-1], [keyi+1, end]
if (keyi + 1 < end)
{
StackPush(&st, keyi+1);
StackPush(&st, end);
}
if (begin < keyi - 1)
{
StackPush(&st, begin);
StackPush(&st, keyi-1);
}
}
StackDestroy(&st);
}
结语：快排就是吊！！！用心文章（写这么多玩意）