2）挖坑法
注：基本操作过程如图示
- 实现代码：
// 快速排序挖坑法 int PartSort2(int* a, int left, int right) { int mid = GetMidIndex(a, left, right); Swap(&a[mid], &a[left]);//使得中间值永远在最左，便于决定谁先走 int key = a[left];//保存key值（基准值） int pivot = left;//保存坑下标 while (left < right) { //右边先找 while (left<right && a[right]>=key) { right--; } //填坑 a[pivot] = a[right]; pivot = right; //再从左边找 while (left < right && a[left] <= key) { left++; } //填坑 a[pivot] = a[left]; pivot = left; } //相遇 a[pivot] = key; return pivot; }
3）前后指针法
注：基本操作过程如图示
- 实现代码：
// 快速排序前后指针法（推荐） int PartSort3(int* a, int left, int right) { int mid = GetMidIndex(a, left, right); Swap(&a[mid], &a[left]); //初始化前后指针 int cur = left+1, prev = left; while (cur < right) { if(a[cur]<a[left] )//找到比基准值小的 Swap(&a[++prev], &a[cur]); cur++; } Swap(&a[prev], &a[left]);//遍历结束将基准值放在定位点 return prev; }
注：推荐掌握，简单易于操控
4）优化
- 三数取中：
- 如果基准值取到的是待排序列中的中位数，对于快排来说效率是最优的
如果基准值取到的是待排序列中的最大或最小，对于快排来说效率是最差的
为了优化这种特殊情况，我们在取基准值时会采取三数取中，即堆待排序序列的开始处，末尾处和中间处位置的数据进行比较，得到排中的数据，尽量使得快速排序的效率达到理想状态O(N*logN)
- 实现代码：
int GetMidIndex(int* a, int left, int right)//优化快排(避免特殊情况造成效率降低) { int mid = right + (left - right) >> 1;//获取中间下标（注意避免和溢出） if (a[mid]>a[left])//返回中等数据的下标 { return a[mid] < a[right] ? mid : right; } else//a[mid]<=a[left] { return a[left] < a[right] ? left : right; } }
整体实现代码：
//快排 void QuickSort(int* a, int left, int right) { //当区间只有一个元素或没有元素时不需要排序了 if (left >= right) return; //遍历一趟进行交换排序 int mid=PartSort3(a, left, right); //递归排序左右区间 QuickSort(a, left, mid - 1); QuickSort(a, mid+1, right); }
- 小区间优化：
当待排序数组的区间很小时，递归开辟的函数栈帧数量时很大的，很多时甚至可能造成栈溢出
为了解决这一问题，当区间小到一定程度时，我们选择使用希尔排序，小到一定程度时待排序数列已经快接近有序，而希尔排序对于接近有序数列的排序时非常高效的
- 实现代码：
//快排+局部优化 void QuickSort1(int* a, int left, int right) { if (left >= right)//当区间只有一个元素或没有元素时递归结束 return; if (right - left + 1 <= 10) { InsertSort(a + left, right - left + 1); } else { int mid = PartSort3(a, left, right);//进行一趟交换排序 QuickSort1(a, left, mid - 1);//递归交换排序 QuickSort1(a, mid + 1, right); } }
- 快速排序的特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
3、快排非递归
- 基本思想;
对于递归函数在内存实际上是在栈中进行开辟函数栈帧，这里我们使用数据结构中的栈来模拟内存中的栈，从而实现快排的非递归
- 实现代码
// 快速排序 非递归实现 void QuickSortNonR(int* a, int left, int right) { //首先构建一个栈（C语言来说需要自己实现） ST st; StackInit(&st); StackPush(&st, left);//将左右区间入栈 StackPush(&st, right); while (!StackEmpty(&st)) { int end = StackTop(&st);//读取区间数据 StackPop(&st); int begin = StackTop(&st); StackPop(&st); int mid = PartSort3(a, begin, end);//排序（排好基准值） //划分基准值的左右区间 int begin1 = mid + 1, end1 = end; //先入右边区域（栈的特点是先入后出） if (end1 - begin1 + 1 > 1) { StackPush(&st, begin1); StackPush(&st, end1); } //再将左边区域入栈 int begin2 = begin, end2 = mid-1; if (end2 - begin2 + 1 > 1) { StackPush(&st, begin2); StackPush(&st, end2); } } //到空栈则排序结束 StackDestroy(&st);//栈销毁 }
