[AcWing]快速排序
代码已经在 GITHUB 开源,👉点击直达👈。
〇、算法步骤
快速排序算法本质上属于分治算法的一种:
- 每次排序时选取一个基准(通常选取位于数组中间的那个值效率更高)。
- 将小于或等于基准的数全部放到基准点的左边,将大于或等于基准的数全部放到基准的右边。
- 完成上一步后,会得到两个“整体上有序”的子数组。
- 再分别递归处理这两个子数组,直至所有元素完成排序。
一、算法模板
这里只给出其中一个模板,便于理解上述算法原理的文字内容。
1 |
|
二、边界问题
在 AcWing 上有大佬给出了快速排序算法的证明与边界分析,这个比较复杂,建议直接背模板。
能弄懂原理最好,但是我们在编程中往往没有那么多时间去推导边界问题。时间即生命,所以爱惜生命,背个模板不过分😋,主打一个听劝!
三、算法练习题
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 SeaEpoch!
评论