「数据结构」八大排序(超详解 附动图 源码)(12)

代码如下：
// 快速排序前后指针法int PartSort3(int* a, int left, int right){ //1.将基准值定在left int keyi = left; int prev = left; int cur = left 1; while (cur <= right) { if (a[cur] < a[keyi] && prev != cur) { Swap(&a[prev], &a[cur]); } cur ; } Swap(&a[prev], &a[keyi]); //2.将基准值定在right /*int keyi = right; int prev = left - 1; int cur = prev 1; while (cur <= right) { if (a[cur] < a[keyi] && prev != cur) { Swap(&a[cur], &a[prev]); } cur ; } Swap(&a[keyi], &a[ prev]); return prev;*/}void QuickSort(int* a, int left, int right){ if (left >= right) { return; } int keyi = PartSort2(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right);}

6.4快速排序优化

上面就是快速排序递归的三种方法。
但是上面的程序还有一些缺陷：
在基准值的选择上，如果选择的基准值为恰好为最小值，会进行不必要的递归。
在排序大量有序数据或者接近有序数据时，效率会比较低，甚至可能会出现程序崩溃的情况。
这是因为在排序有序数据时，快速排序的递归调用次数过多，会导致栈溢出的情况。
为了解决这些问题，这里有两种优化方法：
三数取中法选基准值 递归到小的子区间时，可以考虑使用插入排序
1.即在在起始位置，中间位置，末尾位置中选出中间值，作为基准值。