Sort Colors，颜色排序
2024-08-28 11:55:27
问题描述：Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
就是把三种颜色相同的放在一起，0，1，2，代表三种颜色，按0，1，2排序。
算法分析：其实就是数组排序的问题，但是数组元素只有三种，所以，可以采用快速排序的思想，设置两个指针，先把0颜色放在最左边，然后把1颜色放在次左边。
也可以直接使用快速排序，只不过时间复杂度有点高，并且栈溢出。
public class SortColors
{
public static void sortColors(int[] nums)
{
int start = 0;
int end = nums.length - 1;
while(start <= end)//把0都放在左边
{
if(nums[start] != 0)
{
if(nums[end] == 0)
{
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start ++;
end --;
}
else
{
end --;
}
}
else
{
start ++;
}
} end = nums.length - 1;
while(start <= end)//把1都放在左边
{
if(nums[start] != 1)
{
if(nums[end] == 1)
{
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start ++;
end --;
}
else
{
end --;
}
}
else
{
start ++;
}
}
} //快速排序
public static void sortColors2(int[] nums)
{
quickSort(nums, 0, nums.length - 1);
}
public static void quickSort(int[] nums, int left, int right)
{
int leftIndex = left;
int rightIndex = right;
int pivot = nums[(leftIndex + rightIndex)/2];
while(leftIndex <= rightIndex)
{
while(nums[leftIndex] < pivot)
{
leftIndex ++;
}
while(nums[rightIndex] > pivot)
{
rightIndex --;
}
if(leftIndex <= rightIndex)
{
int temp = nums[leftIndex];
nums[leftIndex] = nums[rightIndex];
nums[rightIndex] = temp;
leftIndex ++;
rightIndex --;
}
if(leftIndex < right)
{
quickSort(nums, leftIndex, right);
}
if(rightIndex > left)
{
quickSort(nums, left, rightIndex);
}
}
}
}
最新文章
- canvas变幻曲线
- 剑指offer三: 斐波拉契数列
- BestCoder 1st Anniversary($) 1003 Sequence
- 【转】Linux内核调试方法总结
- char与byte差异
- office web apps部署（二）
- UVA 11149 Power of Matrix
- php最新微信扫码在线支付接口。ecshop和shopex,shopnc下完美无错
- 《PHP扩展及核心》
- Android自定义控件之日历控件
- api接口开发跨域注意事项和设置
- 1.3if判断语句+while和for循环语句+购物车作业
- zabbix使用percona的mysql监控模板监控
- PlainElastic.Net
- [HEOI2012]采花
- 转：PHP环境搭建 - Linux
- tomcat 内存溢出原因分析及解决
- 把python脚本打包成win可执行文件
- 第一章 MATLAB环境
- 12-15winform--窗体