10.选择排序，以及优化

进行第一次选择排序，把数组中最小的数与数组下标为0的数字进行替换进行第二次选择排序，就把数组中第二小的数字与数组下标为1的数字进行替换进行第三次选择排序，就把数组中第三小的数字与数组下标为2的数字进行替换进行第n次选择排序，就把数组中第n小的数字与数组下标为n-1的数字进行替换一个大小为n的数组，选择排序的次数为n-1次这里经过我们的测试，选择排序和冒泡排序虽然时间复杂度都是n^2 ,但是实际情况下选择排序是优于冒泡排序的 package com.qin.sort; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; //选择排序 结论：实际得出结果 选择排序，是优于冒泡排序的 public class SelectSort { //选择排序的时间复杂度也是n的平方 public static void main(String[] args) { int [] arr = {101,34,119,1}; int [] arr2 = {101,34,119,1}; System.out.println("排序前"); System.out.println(Arrays.toString(arr)); selectSort(arr); System.out.println("============="); System.out.println("一次解决"); selectSort2(arr2); //测试选择排序的速度 int [] arr3 = new int[80000]; for (int i = 0; i < 80000; i++) { //创建一个数组大小为80000 arr3[i] = (int)(Math.random()*80000000); //赋予随机数 } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); selectSort2(arr3); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("执行前的时间是"+date1Str); System.out.println("执行后的时间是"+date2Str); } //选择排序 public static void selectSort(int [] arr){ //使用逐步推倒的方式来，讲解排序 //第一轮，找到最小的 //原始数组：101,34,119,1 //第一次排序： 1,34,119,101 // 算法 先简单--》在复杂 //第一轮 int minIndex = 0; int min = arr[0]; //假定最小的是数组下标为0的数字 for (int i = 0 + 1; i < arr.length; i++) { if (min>arr[i]){ //说明我们假定的这个值并不是最小的 min = arr[i]; //重置min minIndex = i; //重置minIndex } } //将最小值，放在arr[0],交换 arr[minIndex] = arr[0]; arr[0] = min; System.out.println("第1轮后"); System.out.println(Arrays.toString(arr)); //打印数组 //第二轮 minIndex = 1; min = arr[1]; //由于下标为0的数字，已经是最小的了，所以现在我们比较第二小的，第二小的与下标为1的数字替换 for (int i = 0 + 2; i < arr.length; i++) { if (min>arr[i]){ //说明我们假定的这个值并不是最小的 min = arr[i]; //重置min minIndex = i; //重置minIndex } } //将最小值，放在arr[0],交换 if (minIndex!=1){ //优化，这里做一个判断，如果index!= 1 说明最小的数字不是下标为1的数字，我们才有替换的必要，不然不需要替换 arr[minIndex] = arr[1]; arr[1] = min; } System.out.println("第2轮后"); System.out.println(Arrays.toString(arr)); //第三轮 minIndex = 2; min = arr[2]; for (int i = 0 + 3; i < arr.length; i++) { if (min>arr[i]){ //说明我们假定的这个值并不是最小的 min = arr[i]; //重置min minIndex = i; //重置minIndex } } //将最小值，放在arr[2],交换 if (minIndex!=2){ //优化 arr[minIndex] = arr[2]; arr[2] = min; } System.out.println("第3轮后"); System.out.println(Arrays.toString(arr)); //数组大小为4，所以我们只需要排序3次即可 } //选择排序2 public static void selectSort2(int [] arr){ 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]; minIndex = j; } } if (minIndex!= i){ arr[minIndex] =arr[i]; arr[i] = min; } //System.out.println("第"+(i+1)+"轮过后"); 测试的时候我们把他注释一下，不然打印8w次也挺麻烦的 //System.out.println(Arrays.toString(arr)); } } } 结果：

同样是对8w个数据进行有小到大的排序，冒泡排序需要十几秒，而选择排序只需要一到两秒，可以参考 https://blog.csdn.net/qq_46049600/article/details/108956296 冒泡排序的消耗时间