选择排序概念
选择排序也是一种交换排序算法,和冒泡排序有一定的相似度,因此个人认为选择排序可以视为冒泡排序的一种改进算法。它的思路是这样的:
设现在要给数组arr[]排序,它有n个元素。
1对第一个元素(Java中,下标为0)和第二个元素进行比较,如果前者大于后者,那么它一定不是最小的,但是我们并不像冒泡排序一样急着交换。我们可以设置一个临时变量a,存储这个目前最小的元素的下标。然后我们把这个目前最小的元素继续和第三个元素做比较,如果它仍不是最小的,那么,我们再修改a的值。如此直到和最后一个元素比较完,可以肯定a存储的一定是最小的元素的下标。
2.如果a的值不为0(初始值,即第一个元素的下标),交换下标为a和0的两个元素。
3.重复上述过程,这次从下标为1的元素开始比较,因为下标为0的位置已经放好了最小的元素了。
4.如此直到只剩下最后一个元素,可以肯定这个元素就是最大的了。
5.排序完成。
很显然,这个算法也需要n-1轮排序。
需要注意的是,以上阐述的只是每次找最小值的办法。实际上也可以每次找最大值,不过那就需要每次放到数组尾巴上了。
Java实现代码:
SelectArray.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | package ch02;
public class SelectArray {
private long[] arr;
private int elems;
public SelectArray() {
arr = new long[50];
}
public SelectArray(int max) {
arr = new long[max];
}
public void insert(long value) {
arr[elems] = value;
elems++;
}
public void display() {
for (int i = 0; i < elems; i++) {
System.out. print (arr[i] + " " );
}
System.out.println();
}
public void selectSort(){
int min = 0;
long tmp = 0L;
for (int i = 0; i < elems -1; i++){
min = i;
for (int j = i + 1; j < elems; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
}
|
Salin selepas log masuk
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | package ch02;
public class TestSelectArray {
public static void main(String[] args) {
SelectArray sArr = new SelectArray();
sArr.insert(89);
sArr.insert(54);
sArr.insert(667);
sArr.insert(7);
sArr.insert(12);
sArr.insert(43);
sArr.insert(12);
sArr.display();
sArr.selectSort();
sArr.display();
}
}
|
Salin selepas log masuk
结果:

更多Java实现选择排序算法的实例教程相关文章请关注PHP中文网!