1、简单介绍

选择排序（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次，得到一个按排序码从小到大排列的有序序列。

2、源码

  1. package com.study.sort;
  3. import java.util.Arrays;
  5. public class selectSort {
  7.     public static void main(String[] args) {
  8.         int[] arr = {50,40,101,34,99,1};
  9.         selectSort(arr);
  10.     }
  12.     public static void selectSort(int[] arr){
  14.         //选择排序的时间复杂度为(n^2)
  15.         for (int i = 0; i < arr.length - 1; i++) {
  16.             int minIndex = i;//假定最小值得下标为minIndex
  17.             int min = arr[i];//假定最小值为min
  18.             for (int j = i+1; j < arr.length; j++) {
  19.                 if (min > arr[j]){//说明假定的最小值不是最小值
  20.                     min = arr[j];//重置min
  21.                     minIndex = j;//重置下表
  22.                 }
  23.             }
  24.             if (minIndex != i){//说明下标被重置了,交换
  25.                 arr[minIndex] = arr[i];
  26.                 arr[i] = min;
  27.             }else {
  28.                 break;
  29.             }
  30.             System.out.println("第"+(i+1)+"轮交换："+ Arrays.toString(arr));
  31.         }
  33.     }
  34. }

3、运行结果

图片.png

4、测试选择排序

之前的冒泡排序对80000个随机数进行排序，花费了11s
图片.png

选择排序对80000个随机数排序只花费了2s，选择排序比冒泡排序速度快是很多

图片.png

测试源码**

  1. package com.study.sort;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. public class selectSort {
  8.     public static void main(String[] args) {
  9.         /*int[] arr = {50,40,101,34,99,1};
  10.         selectSort(arr);*/
  12.         int[] arr = new int[80000];
  13.         Random random = new Random();
  14.         for (int i = 0; i < 80000; i++) {
  15.             arr[i] = random.nextInt(800000000);
  16.         }
  18.         long l1 = System.currentTimeMillis();
  20.         selectSort(arr);
  22.         long l2 = System.currentTimeMillis();
  24.         System.out.println("选择排序对"+arr.length+"个数据排序所花费的时间为："+(l2-l1)/1000+"s");
  25.     }
  27.     public static void selectSort(int[] arr){
  29.         //选择排序的时间复杂度为(n^2)
  30.         for (int i = 0; i < arr.length - 1; i++) {
  31.             int minIndex = i;//假定最小值得下标为minIndex
  32.             int min = arr[i];//假定最小值为min
  33.             for (int j = i+1; j < arr.length; j++) {
  34.                 if (min > arr[j]){//说明假定的最小值不是最小值
  35.                     min = arr[j];//重置min
  36.                     minIndex = j;//重置下表
  37.                 }
  38.             }
  39.             if (minIndex != i){//说明下标被重置了,交换
  40.                 arr[minIndex] = arr[i];
  41.                 arr[i] = min;
  42.             }else {
  43.                 break;
  44.             }
  45.             //System.out.println("第"+(i+1)+"轮交换："+ Arrays.toString(arr));
  46.         }
  48.     }
  49. }