C++实现 快速排序（可以通过leetcode！）

起因代码一代码二代码三总结

起因

我本是一个默默刷题的小菜鸡，从没想到自己会有写博客的一天。故事是这样的，在leetcode做到了和选择排序思想相关的题目，便想着先复习（学习）选择排序，在各位前辈的文章中，我很快地就自以为掌握了快速排序的思想，在vs上写出了快排的函数，用一个数组检验正确后就没管它了。 然而，今天在做第215题（数组中的第K个最大元素）时，想着先用快速排序的暴力解法。但，我提交时显示解答错误，有案例没有通过。当时（快排）我用的是代码一： 啰嗦了一大堆，总之就是，记录我今天的快排学习心（beng）路（kui）历程，

代码一

快速排序的思想我就不赘述了，前辈们讲解的都特别好，很好理解。以下的代码来源于： 理论部分和代码注释部分都特别浅显易懂 （为了找bug我对照着改了）应该是一模一样的。

#include<iostream> #include<algorithm> using namespace std; void quickSort(int a[],int left,int right) { if (left >= right) return; int i, j, base,m; i = left; j = right; base = a[left]; while (i < j) { if (i < j && a[j] >= base) j--; if (i < j && a[i] <= base) i++; if (i < j) { swap(a[i], a[j]); } } a[left] = a[i]; a[i] = base; quickSort(a, left, i - 1); quickSort(a, i + 1, right); }

我用以上代码（非全部）在leetcode上提交时： 根据提示，我用数组B{-1,2,0}在vs里检验，果然发现了问题： 这个函数对数组B的排序是错误的，因为本人水平极其有限，看不问题在哪，于是试图去原文的评论区寻找答案。结果是并未有前辈讨论相关问题，而我却被评论区的一份改进代码所吸引了，所以我又试了一次…

代码二

这个其实是优化了比较的基数，不是固定地选取区间的第一个值，提高快排的效率，并且把递归放在了函数的末尾，避免产生不必要的递归。

```cpp #include<iostream> #include<algorithm> using namespace std; void quickSort(int a[], int left, int right) { if (left >= right) return; int i, j, base, m; i = left; j = right; m = (i + j) / 2; if (a[i] > a[j]) swap(a[i], a[j]); if (a[m] > a[j]) swap(a[m], a[j]); if (a[m] > a[i]) swap(a[m], a[i]); base = a[i]; while (i < j) { if (i < j && a[j] >= base) j--; if (i < j && a[i] <= base) i++; if (i < j) { swap(a[i], a[j]); } } if (left < i) { swap(a[left], a[i]); quickSort(a, left, i - 1); quickSort(a, i + 1, right); } }

我在vs里用数组B检验通过了，再次去leetcode提交： 再一次根据提示，用了数组C{ 5,2,4,1,3,6,0 }去检验： 唉，本来想着是飞快地暴力解完之后去学习partition 减治和堆地方法，确没想到卡在快排上这么旧，今天非得和它磕到底才行。我又上网学习了一番，便有了代码三：

代码三

原文链接：这篇博文写的也特别好 参考的是原文中的实现方法二：

#include<iostream> #include<algorithm> using namespace std; void quickSort(int a[], int left, int right) { int i = left; int j = right; int temp = a[i]; if (i < j) { while (i < j) { while (i < j && a[j] >= temp) j--; if (i < j) { a[i] = a[j]; i++; } while (i < j && temp > a[i]) i++; if (i < j) { a[j] = a[i]; j--; } } a[i] = temp; //把基准数放到i位置 quickSort(a, left, i - 1); quickSort(a, i + 1, right); } }

用之前的错误案例检测： 全部正确，提交： 可终于通过了，学习学习学习！！！

总结

自以为学习了快排的思想，就能轻易地写出完全正确的代码，实际上要注意的细节部分太多了。 代码一中的思想是，当 j 找到 < 基准的数 && i 找到 > 基准的数，交换 i 和 j 的值，最后 i 和 j 相遇的位置，和 temp值交换。 代码三中的思想（个人感觉）像是填空，把基准（temp，也是 i 的初始位置）拿出来，j 先走，找到小值，填入；i 再走，找到大值，填入之前 j 的位置，这样交换。最后把 temp 放入 i 的位置。（这个似乎是我们数据结构书本里的思想，啊） 但我还是没想通为什么同时交换的方法会错（晚上再努力想想），但确实感觉一个一个换更靠谱，不容易漏（针对仅有3个或其他比较特殊的情况）？ “小乔，要努力变强~” 加油努力奋斗，要学习的还有好多！！