143. Sort Colors II

Description

Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.

You are not suppose to use the library's sort function for this problem.

k <= n

Example

Example1

Input:

[3,2,2,1,4]

4

Output:

[1,2,2,3,4]

Example2

Input:

[2,1,1,2,2]

2

Output:

[1,1,2,2,2]

Challenge

A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory. Can you do it without using extra memory?

思路：

这个题非常有趣，如果直接用快排也可以得到结果，但是时间复杂度是O(nlogn)，参数k的给定就是用来将时间复杂度优化到O(nlogk)的，具体做法就是pivot用k来划分，这里另外一点与快排不一样的是，左边指针在移动的条件是小于等于，而快排的是小于，据说是因为pivot选的时候偏左？

另外题目中提到的另一种计数排序，其时间和空间复杂度均是O(n + k)， k是待排序的整数的范围。注意计数排序只适用于确定数目范围的排序，是一种不基于比较的排序。

代码：

计数排序的代码