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

//三数取中int MidIndex(int* a, int left, int right){ int mid = (left right) / 2; //防止mid越界 //int mid = left (right - left) / 2; if (a[left] < a[right]) { if (a[mid] < a[left]) { return left; } else if (a[mid] > a[right]) { return right; } else { return mid; } } else { if (a[mid] > a[left]) { return left; } else if (a[mid] < a[right]) { return right; } else { return mid; } }}
2.类似于二叉树，每个子树都会进行一次递归调用，越到下面递归调用会越多。为了减少递归调用，当到递归到下层时，我们可以使用其他的排序来替代。这里我们使用插入排序。

以前后指针法为例，完整代码为：
// 快速排序前后指针法int PartSort3(int* a, int left, int right){ int mid = MidIndex(a, left, right); //将基准位置调整至最左边 Swap(&a[mid], &a[left]); //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; } //小区间优化，，减少递归次数 if (right - left 1 < 10) { InsertSort(a left, right -left 1); } else { int keyi = PartSort3(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); }}