前言
选择排序改进了冒泡排序，将必要的交换次数从减少到
.不幸的是比较次数仍保持为
.
一、选择排序
进行选择排序就是把所有的元素扫描一趟，从中挑出最小的元素，最小的元素和队列最左端的元素交换位置，即放到0号位置。现在最左端的元素是有序的，不需要再交换位置了。（注意，这个算法中有序的元素都排在队列的左边，而冒泡排序则是排在队列右边）
在这里插入图片描述
[图片上传失败...(image-cf588d-1628695699101)]
排序代码如下：
public void selectionSort(){
int out,in , min;
for (out = 0;out < arr.length;out++){
min =out;
for (in=out+1;in < arr.length ;in++){
if (arr[in] < arr[min]){
min =in;
}
}
swap(out , min);
}
}
外层循环用循环变量out，从数组下标0开始向高位增长，内层循环用循环变量in，从out所指位置开始，同样向右移位。
在每一个in的新位置，数据项a[in]和a[min]进行比较。如果a[in]更小，则min被赋值为in的值。在内层循环的最后，min指向最小项，然后交换out和min指向的数组数据项。
完整代码如下。
public class SelectSort {
private int[] arr;
public SelectSort(int[] arr) {
this.arr = arr;
}
public void selectionSort(){
int out,in , min;
for (out = 0;out < arr.length;out++){
min =out;
for (in=out+1;in < arr.length ;in++){
if (arr[in] < arr[min]){
min =in;
}
}
swap(out , min);
}
}
private void swap(int one , int two){
int temp = arr[one];
arr[one] = arr[two];
arr[two] = temp;
}
}
测试
public class Main {
public static void main(String[] args) {
Random random = new Random();
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("排序前："+Arrays.toString(arr));
SelectSort selectSort = new SelectSort(arr);
selectSort.selectionSort();
System.out.println("排序后："+Arrays.toString(arr));
}
}
排序前：[55, 39, 74, 11, 64, 8, 35, 3, 78, 43]
排序后：[3, 8, 11, 35, 39, 43, 55, 64, 74, 78]
总结
选择排序和冒泡排序执行了相同的比较：。对于10个数据项，需要45次比较。然而，10个数据项只需要少于10次交换。选择排序无疑更快，因为它进行的交换少得多。
