寻找算法
在数据中有负数有正数找一个算法要求时间最短.只要把负数排在正数前面打印出来就行了 问题点数：20、回复次数：5Top
1 楼Nomad_K（细菜）回复于 2006-06-05 14:47:05 得分 0
冒泡排序Top
2 楼chouy（chouy）回复于 2006-06-05 15:52:33 得分 10
快速交换排序,时间复杂度O(n).
public class QuickSort
{
public static int[] sort(int[] arr)
{
int min = 0;
int max = arr.length - 1;
System.out.println("min = " + min +" max = " + max);
while (min < max)
{
if (arr[min] < 0) // 应该写成while的,但老是出错,我算法基础太差了!下同
{
min = min + 1;
}
if (arr[max] >= 0)
{
max = max - 1;
}
int temp = arr[min];
arr[min] = arr[max];
arr[max] = temp;
if (max - 1 == min)
break;
}
return arr;
}
public static void main(String[] args)
{
int[] array = new int[] { 0, 2, -1, -3, 1, -5, -8, -10, 2, -20, 3};
System.out.println(Arrays.toString(sort(array)));
}
}
Top
3 楼chouy（chouy）回复于 2006-06-05 15:54:37 得分 0
输出:
min = 0 max = 10
[-20, -10, -1, -3, -8, -5, 1, 2, 2, 0, 3]Top
4 楼chouy（chouy）回复于 2006-06-05 16:15:34 得分 10
刚才的程序可能有问题!
再改了一下,用了while,应该会快一点儿.
import java.util.Arrays;
public class QuickSort
{
/**
* @param arr
* 被排列的数组
* @param sign
* 排列数组的值,本例中是0
*/
public static int[] sort(int[] arr, int sign)
{
int min = 0;
int max = arr.length - 1;
System.out.println("min = " + min + " max = " + max);
while (min < max)
{
while (arr[min] < sign)
{
min = min + 1;
if (min == max)
break;
}
while (arr[max] >= sign)
{
max = max - 1;
if (min == max)
break;
}
int temp = arr[min];
arr[min] = arr[max];
arr[max] = temp;
min++;
max--;
}
return arr;
}
public static void main(String[] args)
{
int[] array = new int[] { -2, -1, 11, 1, 0, 2, -1, -3, 1, -5, -8, -10, 2,
-20, 3, -20, -2, 5, 29, 22,-22 };
System.out.println(Arrays.toString(sort(array, 0)));
}
}Top
5 楼yifonger（逸枫）回复于 2006-06-05 17:32:39 得分 0
int[] array = new int[] { -2, -1, 11, 1, 0, 2, -1, -3, 1, -5, -8, -10, 2,
-20, 3, -20, -2, 5, 29, 22,-22 };
Arrays.sort(array);
System.out.println("最少的数："+array[0]+" 最大的数："+array[array.length-1]);
Top
