霍尔版本快速排序的简单梳理
我们霍尔版本排序的快速排序动图如下，每次排序一个数字。
霍尔版本的最坏情况：o(N^2)的快速排序
最坏的情况是什么呢？就是原来这个数组是有序的或者是逆序的，因为我们每次取中间值的时候一般会去取第一个数值来当我们的中间值，这时候我们的快速排序就不是很快了，所以我们如果要排除这种情况我们就可以去使用一个三数取中的逻辑来保证我们取到的数是相对合理的。下面的代码是最简单的快速排序的实现。
//快速排序测试1
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
return;
assert(a);
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
while (a[end] >= a[keyi] && begin < end)
end–;
while (a[begin] <= a[keyi] && begin < end)
begin++;
Swab(&a[end], &a[begin]);
}
Swab(&a[keyi], &a[begin]);
keyi = begin;
QuickSort1(a, left, keyi – 1);
QuickSort1(a, keyi + 1, right);
}
就像【8，7，6，5，4，3，2，1】这一组数据，我们需要让右边找小的，左边找大的，然后交换数值。
在这样走过一次，keyi之前的值都会比keyi位置的值小，keyi后面的值都会比keyi位置的值大，这就是一次快速排序的过程，但是我们发现上面这组数据是逆序的，让我们排成正序的话我们每次排序都会是一次，时间复杂度就是o（N^2)，为了避免上面这样最坏的情况出现，我们可以采取一个三数取中的策略来帮助代码，让排序的时候每次取值不再固定为第一个位置的值。
三数取中和小区间优化的作用
我们就可以把最坏的这种情况最大的规避开来。如何实现呢？
我们知道这个区间，然后我们可以知道开始的位置还有最末尾的位置，知道这两个位置，我们让他们两个相加，再除以2，就得到了中间位置。然后我们看看这三个位置哪个值是适中的。
/////////注意：请注意注释的位置，拷贝的时候请认真分析位置是否正确。
//三数取中
int GetMid(int* a, int left, int right)
{
assert(a);
int mid = (left + right) / 2;
//如果左边大于中间
if (a[left] > a[mid])
{
//left > mid && mid > right 这时候mid绝对是中间值
if (a[mid] > a[right])
{
return mid;
}
//left > mid && left < right -> right > left > mid
//所以中间值是left
else if (a[left] < a[right])
{
return left;
}
//这时候中间值就是right
else
{
return right;
}
}
else // a[left] <= a[mid]
{
//// right > mid >= left
if (a[right] > a[mid])
{
return mid;
}
//// right <= mid left <= mid -> mid > right > left
else if (a[right] > a[left])
{
return right;
}
//// mid > left > right
else
{
return left;
}
}
}
为什么小区间优化可以大大降低递归次数防止栈溢出呢
如果我们只有一个很小的数据需要排序，我们再使用这个快速排序然后层层递归的话，是有点不合适的，关于那些小数据的排序我们完全可以使用插入排序//选择排序//冒泡排序，逻辑既简单，代码又更容易实现，更重要的是，它可以降低快速排序的递归次数，当这个区间小于10的时候，我们选择直接使用插入排序的话，后面的递归就可以不用进行了，这就大大降低了递归的次数。
我们快速排序的递归过程就和上面的满二叉树的节点一样，越往下越多，快速排序如果不写小区间优化的话，最后一次递归结束的条件就是left >= right 就是只有一个数或者是不存在的区间。但是如果我们拥有了小区间优化，当区间到10以内我们就直接不递归直接使用插入排序将数据排序完成，就相当于砍除了上图二叉树最后的几层节点，就让二叉树的节点大大降低了。
把最后一层节点砍除掉那么二叉树的节点就损失了一半，所以就得出了小区间优化，可以大大降低快速排序的递归次数，降低了递归次数防止栈溢出的风险。
//快速排序
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left >= right)
return;
/////////////小区间优化 ///////////////////////
if ((right – left + 1) < 10)
{
InsertSort(a + left, right – left + 1);
return;
}
//////////////////////////////////////////////
int keyi = GetMid(a, left, right);
int begin = left, end = right;
while (begin < end)
{
while (a[end] >= a[keyi] && begin < end)
end–;
while (a[begin] <= a[keyi] && begin < end)
begin++;
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[keyi]);
keyi = begin;
QuickSort(a, left, keyi – 1);
QuickSort(a, keyi + 1, right);
}
