# 第 2 节 切分
# 切分
通过切分，我们要达到这样的效果：把「切分元素」放在排序以后最终应该在的位置。
如下图所示，基准值为
一次切分要实现的效果是：【小于等于基准值的所有元素】基准值【大于等于基准值的所有元素】
- 先选出一个元素，通常是这个数组最开始的那个元素，作为「切分元素」；
- 然后经过一次扫描，使得扫描以后，数组的元素分为两个部分：
- 第 1 部分，都小于切分元素；
- 第 2 部分，都大于等于切分元素；
- 最后我们只要交换一下第 1 个元素和第 1 部分（小于切分元素的部分）的最后 1 个位置的元素，这个 切分元素就呆在了最终它应该呆的位置。
说明：示意图为了表意清晰没有讨论 = 的情况。
切分的思路是这样的：从标定点后面一个一个地比较到底，遇到比标定元素大的，就放过，遇到比标定元素小的，就依次放在标定元素的后面。大放过，小交换。
再看一个例子：
切分过程展示：
最后交换 6 和 5，完成切分。
说明：本节无代码，参考代码会放在「快速排序」的优化一节中。
# 总结
# 快速排序的基本想法
快速排序每一次都排定一个元素（这个元素呆在了它最终应该呆的位置），然后递归地去排它左边的部分和右边的部分，依次进行下去，直到数组有序。
# 快速排序的算法思想
分而治之（分治思想），与「归并排序」不同，「快速排序」在「分」这件事情上不想「归并排序」无脑地一分为二，而是采用了 partition 的方法，因此就没有「合」的过程。
# 与归并排序比较
归并排序不管数组的内容是什么，归并排序总是一分为二地去做排序运算，然后再归并起来。
说明：《算法 4》这本书里面的代码风格是极其不推荐的。代码是写给人看的，应该尽量避免代码个人风格化，采用统一规范的写法，保证易读性，可扩展性。
作者：liweiwei1419 链接：https://suanfa8.com/quick-sort/partition 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。