JAVA学习之选择排序的工作原理是什么

选择排序(Selection sort)是一种简单直观的排序算法。

它的工作原理如下。

首先，在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
如,有一个数组为 int[] arrs=new int[]{2,5,4,3,2,1}

首先,我们在数组里面找出最小的值,存放在数组的第一位arrs[0]
目前arrs[0]=2,分别和索引位置为1,2,3,4,5的元素比较,其中和arrs[5]=1比较时,得到了最小值,并进行交换
第一次排序的结果是{1,5,4,3,2,2}

然后,我们在数组的剩下的位置查找第二小的元素(即剩下数组中的最小元素),存放在数组的第一位后面,也就是arrs[1]的位置
由于经过了一次排序,所以数组现在是这样的{1,5,4,3,2,2}
拿arrs[1]元素的值(注,这个位置的值会变)分别和索引为2,3,4,5的元素比较
arrs[1]=5比较arrs[2]=4,交换位置得{1,4,5,3,2,2}
arrs[1]=4比较arrs[3]=3,交换位置得{1,3,5,4,2,2}
arrs[1]=3比较arrs[4]=2,交换位置得{1,2,5,4,3,2}
arrs[1]=2比较arrs[5]=2,没有交换为{1,2,5,4,3,2}
在此,我们已经在数组的第二个位置存放了第二小的值

下面我们为数组第三的位置,选择第三小的值
由于经过了上次的排序,所以数组现在是这样的{1,2,5,4,3,2}
拿arrs[2]元素的值(注,这个位置的值会变)分别和索引为3,4,5的元素的值比较
arrs[2]=5比较arrs[3]=4,发生的交换,得数组为{1,2,4,5,3,2}
arrs[2]=4比较arrs[4]=3,发生的交换,得数组为{1,2,3,5,4,2}
arrs[2]=3比较arrs[5]=3,发生的交换,得数组为{1,2,2,5,4,3}
在此,我们已经的数组第三的位置存放了第三小的值

依次循环
......
到最后得到的数组为{1,2,2,3,4,5}

整个数组的长度为6,只要我们依次选择好前5个位置存放的值,那么最后一个位置的值就不用比较了,因为最后一个数只有最后一个位置放了,也只能放那个位置
整个数组排列的重点在于选择的时候,在这个位置的元素和其后面的元素比较的时候,在比较没有完成的时候,所选择的那个位置的值也不是固定的;
就好像我们在第二个位置选择值的时候,在没有和后面的元素分别比较完的时候,随着比较的进行,第二个位置arrs[1]的值也一直的变,直到数组比较后最后
才定下了第二小的值为2.
code

public class SelectSort {

public static void main(String[] args) {

 int[] arrs = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
 System.out.println("数组排序前");
 printArray(arrs);

 selectSort(arrs);

 System.out.println("数组排序后");
 printArray(arrs);

}

// 选择排序算法
private static void selectSort(int[] arrs) {
// 选择的索引
for (int i = 0; i < arrs.length - 1; i++) {
// 拿这个索引的元素分别和其后面的元素比较,其中,每比较一次,arrs[i]位置元素的值都有可能发生交换
for (int p = i + 1; p < arrs.length; p++) {
if (arrs[i] > arrs[p]) {
int temp = arrs[i];
arrs[i] = arrs[p];
arrs[p] = temp;
}
}
}
}

// 打印数组方法
public static void printArray(int[] arrs) {
System.out.print("[");
for (int i = 0; i < arrs.length; i++) {
System.out.print(arrs[i]);
if (i != arrs.length - 1) {
System.out.print(",");
}
}
System.out.println("]");
}

}

原作者：zoukankan