Sort Color

题目描述

又叫the dutch national flag problem

变种

1

array of n object with keys that takes one of 4 value, reorder the array so that all object that hae the same key appear together

解法： 跟sort n colors那道有点像，先将最小的和最大的放到两边，这两个的位置就不用变了， 然后recursive sort中间的。

2

Array of n object with Boolean-valued keys, reorder the array that objects have the key False appear first. The relative ordering of objects with key True should not change. Space O(1), time O(n).

要保持的是True的Objects的order,那我们应该从后往前扫，逐一将true的object放到最后，这样true objects的 relative order就不会变了, 因为都是相对后面的放到后面。

我们可以发现的规律是，如果是从前往后扫，那么false的Object的relative order 就不会变，肯定是想遇到的falseobject放到最前面。

解题方法

利用quick sort的Partition的思想

Solution

Reference