时间复杂度O(N2)

选择排序的时间复杂度不会随着样本的改变而改变

说明

每次循环把最小的数选择出来放到前面。 选择排序每次选最小，冒泡排序每次选最大。 选择排序0~[n-1]，1~[n-1], 2~[n-1]….最小的数每次放到前面 冒泡排序0~[n-1], 0~[n-2], 0~[n-3]…. 最大的数放后面

流程说明

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html 每次从m-n的位置上选择一个最小的数，和m位置的数进行交换，直到m==n。相当于是每次从剩余的数中选个最小的数放到最前面 [3, 5, 2, 7, 6]

idx 0 1 2 3 4

第一次: [0-4] 的位置上选一个最小的数，和[0]交换 n次看+比较

第二次: [1-4] 的位置上选一个最小的数，和[1]交换 n-1次看+比较

第二次: [2-4] 的位置上选一个最小的数，和[2]交换 n-2次看+比较

第二次: [3-4] 的位置上选一个最小的数，和[3]交换 n-3次看+比较 时间负责度：等差数列。等差数列 an平方+bn 冒泡排序在j和j+1上做比较和交换，选择排序从剩余的数中选出最小的，不用每次都交换

代码示例

  1. package com.ss;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. /**
  7.  * <p>
  8.  * 选择排序
  9.  * </P>
  10.  *
  11.  * @author: zhangss
  12.  * @since: 2021-01-04
  13.  **/
  14. public class SelectionSort {
  15.     /**
  16.      * 选择排序
  17.      * @param arr
  18.      */
  19.     public static void selectionSort(int[] arr){
  20.         for (int i = 0; i < arr.length; i++) {
  21.             int minIdx = i;
  22.             for (int j = i + 1; j < arr.length; j++) {
  23.                 if (arr[j] < arr[minIdx]){
  24.                     minIdx = j;
  25.                 }
  26.             }
  27.             if (i != minIdx) {
  28.                 swap(arr, i, minIdx);
  29.             }
  30.         }
  31.     }
  33.     /**
  34.      * 交换两个位置的值
  35.      * @param arr
  36.      * @param i
  37.      * @param j
  38.      */
  39.     public static void swap(int[] arr, int i, int j) {
  40.         int temp = arr[i];
  41.         arr[i] = arr[j];
  42.         arr[j] = temp;
  43.     }
  45.     /**
  46.      * 对数器
  47.      * 用来比较上述冒泡排序以后的顺序是否正确
  48.      * @param arr1
  49.      * @param arr2
  50.      * @return
  51.      */
  52.     public static boolean comparator(int[] arr1, int[] arr2){
  53.         if(arr1.length != arr2.length){
  54.             return false;
  55.         }
  56.         Arrays.sort(arr1);
  57.         for (int i = 0; i < arr1.length; i++) {
  58.             if(arr1[i] != arr2[i]){
  59.                 System.out.println(i + "..." + arr1[i]);
  60.                 System.out.println(i + "..." + arr2[i]);
  61.                 return false;
  62.             }
  63.         }
  64.         return true;
  65.     }
  67.     /**
  68.      * 产生数组用来测试冒泡排序方法
  69.      * @return
  70.      */
  71.     public static int[] getArr(){
  72.         Random random = new Random();
  74.         // 若电脑性能有限，生成的数组可以降低长度
  75.         int length = random.nextInt(1000);
  76.         int[] arr = new int[length];
  77.         for(int i = 0; i < length; i++){
  78.             arr[i] = random.nextInt(100);
  79.         }
  80.         return arr;
  81.     }
  83.     public static void main(String[] args) {
  85.         // 循环测试5万次后，确定刚才写的排序没问题
  86.         for (int i = 0; i < 50000; i++) {
  87.             int arr1[] = getArr();
  89.             int arr2[] =  Arrays.copyOf(arr1, arr1.length);
  90.             selectionSort(arr2);
  91.             boolean comparator = comparator(arr1, arr2);
  92.             if(!comparator){
  93.                 System.out.println(Arrays.toString(arr1));
  94.                 System.out.println(Arrays.toString(arr2));
  95.                 System.out.println("排序失败");
  96.             }
  97.         }
  98.     }
  99. }