当前位置： 面试刷题>> 排颜色 (经典算法题500道)
### 题目描述补充
**题目：排颜色**
给定一个整数数组 `colors`，其中每个元素代表一个颜色的编号，要求对这些颜色进行重新排序，使得相同颜色的编号在数组中相邻，并且颜色的相对顺序与原始数组中的相对顺序保持一致（即稳定排序）。
例如，输入数组 `colors = [2, 1, 2, 3, 3, 2]`，则一种可能的输出是 `[1, 2, 2, 2, 3, 3]`，这里 `1`、`2` 和 `3` 都各自聚集在一起，并且保持了它们在原数组中的相对顺序。
### 解题思路
这个问题可以通过使用计数排序（Counting Sort）的思想来解决，但由于计数排序本身不保持稳定性，我们需要稍微修改它以保持稳定性。由于颜色编号的范围可能不是连续的，我们可以使用哈希表（或数组，如果颜色编号范围较小且连续）来记录每个颜色编号的出现次数，并使用一个额外的数组来保存排序后的结果。
### 示例代码
#### PHP 示例
```php
function sortColors($colors) {
$count = array_fill(0, max($colors) + 1, 0); // 初始化计数数组
$index = 0;
// 计数
foreach ($colors as $color) {
$count[$color]++;
}
// 根据计数结果和原始顺序填充结果数组
foreach ($count as $color => $freq) {
while ($freq-- > 0) {
$colors[$index++] = $color;
}
}
return $colors;
}
// 示例
$colors = [2, 1, 2, 3, 3, 2];
$sortedColors = sortColors($colors);
print_r($sortedColors);
```
#### Python 示例
```python
def sortColors(colors):
count = [0] * (max(colors) + 1)
for color in colors:
count[color] += 1
index = 0
for color, freq in enumerate(count):
while freq > 0:
colors[index] = color
index += 1
freq -= 1
# 示例
colors = [2, 1, 2, 3, 3, 2]
sortColors(colors)
print(colors)
```
#### JavaScript 示例
```javascript
function sortColors(colors) {
const count = new Array(Math.max(...colors) + 1).fill(0);
let index = 0;
// 计数
for (let color of colors) {
count[color]++;
}
// 根据计数结果和原始顺序填充原数组
for (let color = 0; color < count.length; color++) {
while (count[color]-- > 0) {
colors[index++] = color;
}
}
return colors;
}
// 示例
let colors = [2, 1, 2, 3, 3, 2];
sortColors(colors);
console.log(colors);
```
**注意**：以上代码直接修改了输入的 `colors` 数组，如果需要保留原数组，可以先复制一份再操作。
**码小课**网站中有更多关于排序算法和面试技巧的相关内容分享，大家可以去学习更多知识。