赞
赏
力扣第 75 题。给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1:
输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
示例 2:
输入:nums = [2,0,1]
输出:[0,1,2]
示例3:
输入:nums = [0]
输出:[0]
示例4:
输入:nums = [1]
输出:[1]
提示:
该题虽然是一个场景题目,实际上抛开该场景,就是对一个数组进行排序。数组里面的元素为 0,1,2。它们的顺序是乱的,需要按照 0,1,2 的方式输出。我们可以考虑使用冒泡排序法来将数组数据排序,冒泡排序的基本思路是将数组中的两个相邻的数据进行比较,如果两个元素反序,就将两个元素换位置,直到遍历到最后没有反序为止。它就像鱼吐泡泡一样,每次得到最大值。
我们以示例1为实例来进行判断,如下:
第一轮排序的时候顺序如下:
2 和 2 比较,2 和 2 相等,所以不需要换位置。
2 和 1 比较,由于 2 比 1 大,需要将 2 和 1 换位置
第一轮遍历全部完成,得到如下结果:
剩下的元素按照上面的流程进行比较,得到如下结果:
class Solution {
public void sortColors(int[] nums) {
for(int i = 0;i< nums.length - 1 ;i++){
boolean isSorted = true;
for(int j =0;j<nums.length - i - 1;j++){
int tmp = 0;
if(nums[j] > nums[j + 1]){
tmp = nums[j];
nums[j] = nums[j + 1];
nums[j+1] = tmp;
isSorted = false;
}
}
if(isSorted){
break;
}
}
}
}
func sortColors(nums []int) {
for i := 0;i< len(nums) - 1 ;i++ {
isSorted := true;
for j := 0;j<len(nums) - i - 1;j++ {
tmp := 0
if nums[j] > nums[j + 1] {
tmp = nums[j]
nums[j] = nums[j + 1]
nums[j+1] = tmp
isSorted = false
}
}
if(isSorted){
break
}
}
}