# 2.2 选择排序（select sorting） #### 一. 定义 选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。 选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr\[0\]---arr\[n-1\]中选取最小值，与arr\[0\]交换，第二次从arr\[1\]---arr\[n-1\]中选取最小值，与arr\[1\]交换，第三次从arr\[2\]---arr\[n-1\]中选取最小值，与arr\[2\]交换，...，第i次从arr\[i-1\]\~arr\[n-1\]中选取最小值，与arr\[i-1\]交换，..., 第n-1次从arr\[n-2\]\~arr\[n-1\]中选取最小值，与arr\[n-2\]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。 #### 二. 代码实现 \`\`\`java /\*\* \* desc 选择排序 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-01-12-11:04 \*\*/ //选择排序 public class SelectSort { public static void main(String\[\] args) { //创建要给80000个的随机的数组 int\[\] arr = new int\[80000\]; for (int i = 0; i \< 80000; i++) { arr\[i\] = (int) (Math.random() \* 8000000); // 生成一个\[0, 8000000) 数 } Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是=" + date1Str); selectSort(arr); Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序后的时间是=" + date2Str); } //选择排序 public static void selectSort(int\[\] arr) { //在推导的过程，我们发现了规律，因此，可以使用for来解决 //选择排序时间复杂度是 O(n\^2) for (int i = 0; i \< arr.length - 1; i++) { int minIndex = i; int min = arr\[i\]; for (int j = i + 1; j \< arr.length; j++) { if (min \> arr\[j\]) { // 说明假定的最小值，并不是最小 min = arr\[j\]; // 重置min minIndex = j; // 重置minIndex } } // 将最小值，放在arr\[0\], 即交换 if (minIndex != i) { arr\[minIndex\] = arr\[i\]; arr\[i\] = min; } } } } \`\`\`