题目
给定一个有n个对象（包括k种不同的颜色，并按照1到k进行编号）的数组，将对象进行分类使相同颜色的对象相邻，并按照1,2，...k的顺序进行排序。
注意事项
You are not suppose to use the library's sort function for this problem.
k <= n
样例
给出colors=[3, 2, 2, 1, 4]，k=4, 你的代码应该在原地操作使得数组变成[1, 2, 2, 3, 4]
分析
其实就是排序，二分法排序
代码
class Solution {
/**
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2(int[] colors, int k) {
if (colors == null || colors.length == 0) {
return;
}
rainbowSort(colors, 0, colors.length - 1, 1, k);
}
public void rainbowSort(int[] colors,
int left,
int right,
int colorFrom,
int colorTo) {
if (colorFrom == colorTo) {
return;
}
if (left >= right) {
return;
}
int colorMid = (colorFrom + colorTo) / 2;
int l = left, r = right;
while (l <= r) {
while (l <= r && colors[l] <= colorMid) {
l++;
}
while (l <= r && colors[r] > colorMid) {
r--;
}
if (l <= r) {
int temp = colors[l];
colors[l] = colors[r];
colors[r] = temp;
l++;
r--;
}
}
rainbowSort(colors, left, r, colorFrom, colorMid);
rainbowSort(colors, l, right, colorMid + 1, colorTo);
}
}
