题目

LeetCode.75.颜色分类（中等）

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

题解

排序解法

直接用排序算法排序数组即可得到结果。

采用不同的排序算法，时间复杂度和空间复杂度各不同。

如果用基于比较的排序算法，平均时间复杂度最低为O(n * log n)，空间复杂度O(1)，例如快速排序、堆排序。

由于数组元素取值就三种情况，是常数个，可以使用不基于元素比较的线性时间排序算法，如计数排序，时间复杂度O(n)，空间复杂度O(n)。

更优的解法

由于元素取值只有极少的常数个，可以发现这里元素归位的过程很像快速排序的划分算法，把不同类型的元素放在轴心元素的两边。

如果只有两个颜色（红色和白色），可以直接用划分了，而一次划分时间复杂度是O(n)，空间复杂度O(1)。

快速排序的划分算法：

双指针分别指向数组开始和末尾。
左指针遇到白色就与右指针交换元素，把白色放在右边，右指针向左前进一位。
右指针遇到红色就与左指针交换元素，把红色放在左边，左指针向右前进一位。
左右指针相遇后，红色和白色都放置在各自的一边了。

划分算法的关键是，遇到不是这个位置的元素，就把它放到属于它的那一类的位置。

可以发现，左指针的左边总是红色元素，右指针的右边总是白色元素。

三个颜色会有什么不同？

那就再增加一个蓝色指针，表示这个指针的左边到红色指针的右边都是蓝色元素。

在用蓝色指针遍历数组时：

发现红色元素，放到红色指针左边。
发现白色元素，放到白色指针右边。
发现蓝色元素，已经在自己这边了，前进一个位置。

蓝色指针和白色指针相遇后，所有颜色就正确归位了。

最终还是一次线性划分就能解决。
时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    fun sortColors(nums: IntArray): Unit {
        var p0 = 0
        var p2 = nums.size - 1
        var p1 = 0
        while (p1 <= p2) {
            when(nums[p1]) {
                0 -> {
                    nums.swap(p0, p1)
                    p0++
                    p1++
                }
                2 -> {
                    nums.swap(p1, p2)
                    p2--
                }
                else -> p1++
            }
        }
    }

    private fun IntArray.swap(i: Int, j: Int) {
        val tmp = this[i]
        this[i] = this[j]
        this[j] = tmp 
    }
}