快速排序
快速排序是所有排序算法中速度最快的一个排序算法（在数据量很庞大的前提下），因此，很多库中自带的sort都是用快速排序做底层实现的，例如qsort和STL中的sort，因此，学习好它是很有必要的
首先说明它的基本思想
基本思路是，选定一个元素为key，经过一系列算法让原本数组中比key小的数据在key的左边，比key大的数据在key的右边，然后递归进入key的左边，在递归函数中重复这个操作，最后就能完成排序，那么第一个关键点就是如何实现让以key为分界点，左右分别是比它大和比它小的？
关于这个算法有很多版本，我们一一介绍
hoare版
快速排序的创始人就是hoare，作为快速排序的祖师爷，hoare在研究快速排序自然写出了对应的算法，那么我们当然要先学习最经典的算法
下面展示hoare算法的示意图
看完演绎图和上面的流程图，大概可以理解hoare算法的基本思路，但其实还有一些问题，比如最后交换的元素(上图中为3) 一定比key小吗？比key大难道不会让大的元素到key的左边吗？
解释上述问题的原因
==其实问题的原因就在于left和right谁先走的问题，在上面算法中是让right先走，这是为什么？==
我们假设中间的元素不是3，而是8 (大于key的都可以) 那么，当right继续向前走的时候就会跳过8，继续向前找，最后最坏的结果会找到left，而left对应的是和前面交换后的比key小的元素，因此这里只要是right先走，最终和right和left相遇的位置一定比key小！
这个算法其实并不好写，需要控制的变量和问题很多，实现过程如下
int PartSort1(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;
}
==注意点==
- keyi的选取是left而不是0，因为后面递归的时候最左边的元素下标不一定是0
- while循环向前/向后寻找时要随时判断left有没有小于right，防止越界
- 返回的是左值，这个左值就是下一次的左边界或右边界、
快速排序的实现
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
后续的三种写法只需要替换掉PartSort1即可
挖坑法
代码实现如下：
int PartSort2(int* a, int left, int right)
{
int key = a[left];
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 hole;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = PartSort2(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
这个实现很简单，没有需要额外注意，相较第一个算法来说更容易理解一些
前后指针法
实现原理如下图所示
代码实现逻辑如下
int PartSort3(int* a, int left, int right)
{
int cur = left+1;
int prev = left;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
++prev;
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
实际上是prev找cur，如果cur指针对应的值小于key，那么就++prev再交换，否则cur就继续前进，这样就能使得cur和prev之间的数据全部为比key大的数据
