目录
前言
快速排序算法（前后指针法版本）的思想编辑
单躺排序逻辑的实现
快速排序算法的实现（前后指针法）
前言
对于快速排序算法的实现，在前面两章已经学习了两种不同的实现方法
数据结构 ——— 快速排序算法的实现（挖坑法版本）-CSDN博客
数据结构 ——— 快速排序算法的实现（hoare版本）-CSDN博客
接下来再学习一种办法，能更加理解快速排序的实现，以及此办法能规避更多的缺陷
快速排序算法（前后指针法版本）的思想
初始时，prev 指针指向序列开头，cur 指针指向 prev 指针的后一个位置
然后判断 cur 指针指向的数据是否小于 key ，若小于，则 prev 指针先向后移一位，然后 cur 指向的内容与 prev 指向的内容交换，然后 cur 指针 ++
直到 cur 指针指向的内容大于或等于 key 时就越过，也就是 cur 指针直接 ++
最后 cur 指针 大于数组长度时，prev 指针指向的数据与 key 交换
这样同样能保证 key 左边的比 key 小，bey 右边的比 key 大
单躺排序逻辑的实现
int PartSort_Pointer(int* a, int left, int right)
{int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}cur++;}// 把 key 放在最终位置Swap(&a[prev], &a[keyi]);return prev;
}因为最开始 cur 指针在 prev 的后一个位置
所以当最开始 cur 就遇到比 key 小的值时，prev 指针 ++ 的话，就和 cur 指针重叠了，这样再交换的话就没有意义了，所以在交换的时候需要判断两个指针是否相等
最后再把 key 放在最终位置即可
快速排序算法的实现（前后指针法）
void QuickSort(int* a, int begin, int end)
{// 前后指针法if (begin >= end) {return;}int key = PartSort_Pointer(a, begin, end);// [begin,key-1] key [key+1,end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}和前两章的递归思路一样，这里就不过多赘述
代码验证：
