数组的排序
像查找一样,排序也是计算机中常用的操作。这里介绍两种方法。
选择排序
假设要按升序排列一个数组。选择排序法先找到数列中最小的数,然后将它放在数列中的最前面。接下来再剩下的数中选择最小数,将它放在第一个的后面,以此类推,直到数列中仅剩一个数为止。
看一张示例图,会讲解得更清楚:
示例图
下面显示了选择排序的程序:
public static int[] SelectionSort(int[] arrays){
//i表示交换的次数,从上面的图中就可以发现交换9次
for (int i = 0; i < arrays.length - 1; i++) {
int temp = 0;//用来保存最小的那个数
int index = i; // 用来保存最小值的索引
// 寻找第i个小的数值
//这一次循环之后,index将获得最小值的索引
for (int j = i + 1; j < arrays.length; j++) {
if (arrays[index] > arrays[j]) {
index = j;
}
}
// 交换位置,将找到的第i个小的数值放在第i个位置上
//将最小值赋值给temp
temp = arrays[index];
arrays[index] = arrays[i];
arrays[i] = temp;
}
return arrays;
}
用下面的语句跟踪该方法
int[] list = {3,5,23,45,1,66};
int[] list2 = SelectionSort(list);
System.out.println(Arrays.toString(list2));
输出结果:
[1, 3, 5, 23, 45, 66]
冒泡排序
在每次遍历数组中,对相邻的两个元素进行比较。如果这一对元素是降序,则交换他们的值;否则,保持值不变。
看一个示例图,有时候图解比文字更清楚:
示例图
下面展示了运用冒泡排序算法对数列{2,9,5,4,8,1,6}进行排序:
public static double[] bubbleSort(double[] arrays){
int temp;
//这里i表示交换的几次,比如上面图中52换到第一位一共进行了三次交换
for(int i = 0;i<arrays.length-1;i++){
//从后向前依次的比较相邻两个数的大小,遍历一次后,把数组中第i小的数放在第j个位置上
//这里j表示交换后它所处的位置,比如,第一次j=3,是因为52跟59交换之后到了3这个位置
//把最后一个数跟前面的数进行比较,一直到i的位置停止
for(int j = arrays.length-1;j>i;j--){
//对相邻的两个数进行比较并交换位置
if (arrays[j - 1] > arrays[j]) {
temp = arrays[j - 1];
arrays[j - 1] = arrays[j];
arrays[j] = temp;
}
}
}
return arrays;
}
用下面语句跟踪上述算法:
double[] myList = {5.0, 4.4, 1.9, 2.9, 3.4, 2.9, 3.5};
double []list = bubbleSort(myList);
System.out.println("My list after sort is: " + Arrays.toString(list));
输出结果:
My list after sort is: [1.9, 2.9, 2.9, 3.4, 3.5, 4.4, 5.0]
网友评论