首先提出一个问题，一个数组，给定一个划分值，如何在不额外申请空间的情况下做到划分值左边的数比划分值小，右边的数比划分值大呢？
- 我们给定一个小于等于区的概念，取数组中的数与划分值作比较，当前数小于等于划分值的时候，当前数与小于等于区下一个数交换，小于等于区扩大一个，当前数跳下一个，当前数大于划分值，小于等于区不扩，当前数跳下一个。一直到当前数越界终止程序，这样就完成了上面的问题。这种问题我们成为inplace问题。
接下来，讲一下荷兰国旗问题，什么事荷兰国旗问题呢？
荷兰国旗问题其实就是上面inplace问题的变型，这里面不仅要分出大与和小于划分值的数，还要分出等于划分值的数。所以我们需要三个分区，大于区小于区和等于区。同样分为以下情况：
当前数小于划分值：当前数于小于区下一个交换，小于区扩大一位，当前数跳下一个
当前数等于划分值：当前数跳下一个
当前数大于划分值：当前数与大于区下一个交换，大于区扩大一位，当前数不变
当前数越界停止，这时候就完成了荷兰国旗问题。
结合快排的原理我们就会发现，快速排序其实就是荷兰国旗的改版，只不过是我们在数组内部随机找到划分值进行分区，然后再各自分区内重复进行相同的工作，直到符合base case的要求。这样就是快速排序。
京公网安备 11010502036488号