这一篇文章主要讲解快速排序前后指针法和非递归实现先把代码放到此处前后指针void part2(int* arr, int* pbegin, int* pend,int keyi) { int prev *pbegin; int cur *pbegin; while (cur *pend) { if (arr[cur] arr[keyi] prev ! cur) { Swap(arr[prev], arr[cur]); } cur; } *pbegin prev; } void QuickSort(int* arr, int left, int right) { if (left right) { return; } if (right - left 10) { InsertSort(arr left, right - left 1); return; } int keyi Mid_Search(arr, left, (left right) / 2, right); Swap(arr[keyi], arr[left]); keyi left; int begin left; int end right; //part1(arr, begin, end, keyi); part2(arr, begin, end, keyi); Swap(arr[begin], arr[keyi]); keyi begin; QuickSort(arr, left, keyi - 1); QuickSort(arr, keyi 1, right); }非递归void _QuickSortNon(int* arr, Stack* ps) { while (!StackEmpty(ps)) { int left StackTop(ps); StackPop(ps); int right StackTop(ps); StackPop(ps); if (left right) { return; } if (right - left 10) { InsertSort(arr left, right - left 1); return; } int keyi Mid_Search(arr, left, (left right) / 2, right); Swap(arr[keyi], arr[left]); keyi left; int begin left; int end right; //part1(arr, begin, end, keyi); part2(arr, begin, end, keyi); Swap(arr[begin], arr[keyi]); keyi begin; //[left,keyi][keyi1,right] if (keyi 1 right) { StackPush(ps, right); StackPush(ps, keyi 1); } if (left keyi) { StackPush(ps, keyi); StackPush(ps, left); } } } void QuickSortNon(int* arr, int left, int right) { Stack st; StackInit(st); StackPush(st, right); StackPush(st, left); _QuickSortNon(arr, st); StackDestroy(st); }前后指针法是另一种快速排序的实现方式但是虽然换了一种方式效率却相较之前没有提升只是变得容易理解。顾名思义前后指针法核心是前后指针prev和cur两个指针首先假设在不三数取中的情况下把left当作keyiprev和cur也初始化为leftcur判断自己值是否小于keyi对应的值若小则prev并交换prev与cur的对应值反之curprev不做处理直到cur超出自己访问区间将prev值与keyi交换接着分治进行下一组排序。相比于上一种写法前后指针显然好理解一点。接下来讲一讲非递归为啥要有非递归假设数组有序那我们快排逻辑在不三数取中前提下就会无休止的调用堆栈导致栈溢出。因为好比你用上一讲的快排方法end找小于key的值怎么也找不到所以一次递归就解决了第一个数递归的深度相当高。而非递归使用栈这数据结构是在堆区中开辟空间堆区的空间相当大不太可能会发生溢出的情况。然后是代码实现首先需要栈这一个数据结构吧然后我们之前递归的本质其实是分区间找到一个相对中间的位置然后分而治之左区间右区间循环往复那又是什么划分了左右区间其实就是我们传的下标那递归的核心就是递归下标吧同理采用非递归我们也要存储区间下标由于下标有左右两边所以应该一次存储两个一次弹出两个直到栈为空就不再进行。栈为啥会为空其实也好理解当我们出现区间就剩一个元素或者区间一个元素都没有的情况是不能入栈的那么这次就相当于只出不进了因此循环往复栈是会为空的。