一、快排的几种实现方法
1.左右指针法
a>算法思想：选定数组的最后一个数作为关键值（key），从左边开始遍历找比key大的，从右边找比key小的，找到后交换左右指针，让比key大的数据向后调，比key小的数据调到前面，等到左右指针相等的时候，把数组的最后一位和指针所指位置交换，这样一趟排序过后，key值的前面都是比它小的数，后面都比它大。此时key相当于划分了它左右两个区间，那么两个区间再次分别像刚才一样进行选key交换，会不断的划分新区间，直至区间只包含一个数，就有序了。
单趟排序的图示
我们知道，每次单趟排序之后将数组分为了两个区间，而每个区间也都需要分别排序，故我们可以考虑用递归去实现。
b>优化：假设每一次选的key值都是数组里最大或者最小的数，那快排就会变得很慢很慢，可以认为变成了冒泡排序，所以，key的选取比较关键，我们希望每次选到的是值比较居中的数，所以，key的选取使用三数取中法，即比较区间的第一个数，中间的数和最后一个数，选出值位于中间的数与最后一位交换，因为我们每次取的key是区间的最后一位，这样就尽可能的保证key的值贴近于中间值。
c>时间复杂度：快排每次都会划分区间，直至区间中只有一个数，这一过程跟二叉树结构比较类似，单趟排序交换数的过程近似相当于遍历了这n个数，外层需要高度次递归，故，时间复杂度为O（n*log n）.
d>空间复杂度：递归了高度次，即空间复杂度为O(log n)
e>代码实现
//左右指针法
int PartSort(int* a,int begin,int end) //单趟排序
{
int left = begin;
int right = end;
int mid = GetBestKey(a,begin,end); //三数取中法得到key
swap(a[mid],a[end]);
int key =a[end];
while (left < right)
{
while (left < right && a[left] <= key)
{
left++;
}
while (left < right && a[right] >= key)
{
right--;
}
if (a[left]>a[right])
swap(a[left],a[right]);
}
swap(a[left],a[end]);
return left;
}
void QuickSortR(int* a,int end) //递归版
{
int mid;
if (begin < end)
{
mid = PartSort(a,end);
QuickSortR(a,mid - 1);
QuickSortR(a,mid + 1,end);
}
}
//key取值的优化
int GetBestKey(int* a,int end)
{
if ((end - begin) < 1)
return end;
int mid = begin + (end - begin) / 2;
if (a[begin] < a[end])
{
if (a[mid] < a[begin])
return begin;
else if (a[mid]>a[end])
return end;
else
return mid;
}
else
{
if (a[end] > a[mid])
return end;
else if (a[mid] > a[begin])
return begin;
else
return mid;
}
}
2.挖坑法
a>算法思想：挖坑法其实和前后指针法也比较相似，区间的最后一个数保存在key里之后，最后一个位置就视为一个坑，先从左边开始找比key大的，找到了放进刚才的坑里，左边又产生了一个新坑，右边找比key小的，找到了填到左边的坑。最后左右相遇于坑处，key放到此处，单趟排序就结束了，之后再递归，和第一种方法一样。所以时间复杂度，空间复杂度和第一种方法一致。
b>优化：对排序整体进行优化，我们知道，当大量数据进行排序时，递归是划算的，可是如果当区间已经被划分的很小的话，不用去递归，改用直接插入排序也很快，因为区间很小，由快排的特性知，此时的小区间接近有序，而接近有序的时候插入排序是O(n)。还节省了快排递归时压栈的开销。（所有的快排方法都可以进行这样的优化）
c>代码实现
//挖坑法进行单趟排序
int PartSort1(int*a,int end)
{
int mid = GetBestKey(a,end);
swap(a[mid],a[end]);
int key = a[end];
int left = begin;
int right = end;
while (left < right)
{
while (left < right && a[left] <= key)
{
left++;
}
a[right] = a[left];
while (left<right && a[right] >= key)
{
right--;
}
a[left] = a[right];
}
a[left] = key;
return left;
}
void QuickSortR(int* a,int end) //递归版
{
int mid;
if (begin < end)
{
mid = PartSort1(a,end);
if (end - begin < 4) //区间数值个数小于4的时候直接插入排序
{
InSertSort(a + begin,end - begin + 1);
}
mid = PartSort2(a,end);
}
}
3.前后指针法
a>算法思想：定义两个指针prev和cur，cur指向区间第一个数，prev指向它的前一个。从左向右找比key小的，若当前数比key大，则cur向前移动，直到找到一个比key小的，此时prev向前移动一位，若prev和cur不指向同一位置，则prev所指位置的数值一定比cur大，所以交换prev和cur所指向的数。等到cur指向了最右边的数，再把最后一个数和prev的下一个位置的数交换，一趟排序就结束了。
//前后指针法
int PartSort2(int*a,int end)
{
int prev = begin - 1;
int cur = begin;
int mid = GetBestKey(a,a[end]);
int key = a[end];
while (cur < end)
{
while (a[cur] < key && ++prev != cur)
{
swap(a[cur],a[prev]);
}
++cur;
}
swap(a[end],a[++prev]);
return prev;
}c>单趟排序后还要继续往下排，之前我们用的都是递归的方法，此处我们把它转化为
非递归，要用到栈。代码如下
void QuickSortNoR(int *a,int end)//非递归
{
assert(a);
stack<int> s;
if (begin < end)
{
s.push(end);
s.push(begin);
while (!s.empty())
{
int left = s.top();
s.pop();
int right = s.top();
s.pop();
int mid = PartSort2(a,left,right);
if (mid - 1 > left)
{
s.push(mid - 1);
s.push(left);
}
if (right > mid + 1)
{
s.push(right);
s.push(mid + 1);
}
}
}
} 快排的三种方式都理解了之后，个人觉得前后指针法最简单，代码实现起来很容易，同时要注意，如果是大量数据排序的话，最好进行一下方法二里面提到的优化，一是能提高效率，二也能防止不断的递归导致栈溢出。 原文链接：https://www.f2er.com/datastructure/382389.html