1、基本思想
第一次从 arr[0] ~ arr[n-1] 中选取最小值，与 arr[0] 交换；第二次从 arr[1] ~ arr[n-1] 中选取最小值，与 arr[1] 交换；第三次从 arr[2] ~ arr[n-1] 中选取最小值，与 arr[2] 交换…。以此类推，总共通过 n - 1 次，得到一个从小到大的有序序列。
2、图解
3、代码实现
package cn.klb.datastructures.sort;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 实现对数组的选择排序
* @Date: Create in 2023/4/3 22:15
* @Modified By:
*/
public class Select {
public static void sort(int[] attr) {
int min; // 保存最小值
int index = 0; // 最小值的索引
// 从 attr[i] 到 attr[attr.length-1] 中找到最小值来和 attr[i]交换
for (int i = 0; i < attr.length - 1; i++) {
index = i; // 假设i索引对应的就是最小值
min = attr[i];
// 寻找最小值的索引
for (int j = i + 1; j < attr.length; j++) {
// 如果找到更小的，跳到那个索引，继续往右走找更小的，直到找不到为止
if (min > attr[j]) {
// 发现attr[j]更小
min = attr[j]; // 更新最小值
index = j; // 更新最小值索引
}
}
// 扫描结束后，最小值和对应的索引肯定确定好了
if (i != index) {
// 如果最小值就是一开始假设的那个，就省的交换了
attr[index] = attr[i];
attr[i] = min;
}
}
}
}
4、时间复杂度
通过代码可以看出：总共有两层for循环，比较操作有一步，更新索引操作有两步。
假设比较次数为C，交换次数为S。
最好的情况下，待排序的序列已经是从小到大排列的。此时，比较次数C=(n+6)(n-1)/2=O(n²)，交换次数S=0=O(1)。
最差的情况下，待排序的序列是从大到小排序的。交不交换都得比较后才知道，所以，比较次数C=(n+6)(n-1)/2=O(n²)，交换次数S=n(n-1)/2=O(n²)。
时间复杂度都是看最复杂的，因此，选择排序的时间复杂度为O(n²)。
5、稳定性
从选择排序的原理就可以看出这个排序一定是不稳定的，比如有一个序列{3,4,3,7,1}，第一轮排序，从序列中找到最小值1和第0个元素3交换位置，一交换，两个3的前后关系就破坏了。所以说，选择排序是不稳定的。
6、测试
package cn.klb.test.datastructurestest;
import cn.klb.datastructures.sort.*;
import org.junit.Test;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 排序测试
* @Date: Create in 2023/4/3 21:32
* @Modified By:
*/
public class SotrTest {
@Test
public void testSelect() {
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 800000);
}
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
Date date1 = new Date();
System.out.println("-----" + sdf.format(date1) + "-----");
//System.out.println(Arrays.toString(arr));
Select.sort(arr);
Date date2 = new Date();
System.out.println("-----" + sdf.format(date2) + "-----");
//System.out.println(Arrays.toString(arr));
// 8万的随机数据进行选择排序，我的电脑花了大约4秒
// 80万的随机数据进行选择排序，我的电脑花了大约4分2秒（比冒泡排序快了几倍）
}
}