1.动画展示

选择.gif

2.思路分析

  1. 第一个跟后面的所有数相比，如果小于（或大于）第一个数的时候，暂存较小数的下标，第一趟结束后，将第一个数，与暂存的那个最小数进行交换，第一个数就是最小（或最大的数）
  2. 下标移到第二位，第二个数跟后面的所有数相比，一趟下来，确定第二小（或第二大）的数

重复以上步骤
直到指针移到倒数第二位，确定倒数第二小（或倒数第二大）的数，那么最后一位也就确定了，排序完成。
image.png
image.png

3.复杂度分析

  1. 不管原始数组是否有序，时间复杂度都是O（n^2），

因为每一个数都要与其他数比较一次，（n-1）^2次，分解：n^2-2n+1, 去掉低次幂和常数，剩下n^2,所以最后的时间复杂度是O(n^2)。

  1. 空间复杂度是O（1）,因为只定义了两个辅助变量，与n的大小无关，所以空间复杂度为O（1）。

    4.代码实现

    最近看的，较容易理解
    1. public static void Select(int[] arr){
    2.      //跟冒泡一样第一轮：同样只需要比较长度-1次
    3.      for (int i = 0; i < arr.length-1; i++) {
    4.          //i代表每轮选择最小元素要交换到的目标索引
    5.          int s = i;//代表最小元素的索引，
    6.          // 一开始认定一开始为i，后面找打更小的再更新s
    7.          for (int j = i+1; j <arr.length ; j++) {
    8.              if (arr[j]<arr[s]){
    9.                  s=j;
    10.              }
    11.          }
    12.          if (s!=i){
    13.              swap(arr,s,i);
    14.          }
    15.          System.out.println(Arrays.toString(arr));
    16.      }
    17.  }
  1. public class SelectSort {
  2.     public static void main(String[] args) {
  3.         int arr[] = {6,7,9,5,2};
  4.         System.out.println("排序前");
  5.         System.out.println(Arrays.toString(arr));
  6.         selectSort(arr);
  7.         System.out.println("排序后");
  8.         System.out.println(Arrays.toString(arr));
  9.     }
  10.     public static void selectSort(int[] arr){
  11.         /**
  12.          * 思路：假设第一个值为最小值，每一轮排序，最小值后面的数与该轮最小值的数进行比较，
  13.          * 如果后面有比这个值还要小，则改变这个设定的最小值为这个值，并交换两个值的索引位置，
  14.          进而交换两个值的位置。
  15.          */
  16.         for (int i = 0; i <arr.length ; i++) {//arr[i]为每轮设定的最小值
  17.             int minIndex = i; //假设第一个值为最小值i
  18.             int min = arr[i];
  19.             for (int j = i + 1; j <arr.length ; j++) {
  20.                 if (min > arr[j]){
  21.                     min = arr[j]; //重置最小值
  22.                     minIndex = j ; //重置最小值的索引
  23.                 }
  24.             }
  25.             if (minIndex != i) { //优化
  26.                 arr[minIndex] = arr[i]; //交换两个值
  27.                 arr[i] = min;
  28.             }
  29.         }
  30.     }
  31. }

推导过程

  1. //使用逐步推导的方式来，讲解选择排序
  2.         //第1轮
  3.         //原始的数组 ：     101, 34, 119, 1
  4.         //第一轮排序 :       1, 34, 119, 101
  5.         //算法 先简单--》 做复杂， 就是可以把一个复杂的算法，拆分成简单的问题-》逐步解决
  7.         //第1轮
  8.         int minIndex = 0;
  9.         int min = arr[0];
  10.         for(int j = 0 + 1; j < arr.length; j++) {
  11.             if (min > arr[j]) { //说明假定的最小值，并不是最小
  12.                 min = arr[j]; //重置min
  13.                 minIndex = j; //重置minIndex
  14.             }
  15.         }
  18.         //将最小值，放在arr[0], 即交换
  19.         if(minIndex != 0) {
  20.             arr[minIndex] = arr[0];
  21.             arr[0] = min;
  22.         }
  24.         System.out.println("第1轮后~~");
  25.         System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
  28.         //第2轮
  29.         minIndex = 1;
  30.         min = arr[1];
  31.         for (int j = 1 + 1; j < arr.length; j++) {
  32.             if (min > arr[j]) { // 说明假定的最小值，并不是最小
  33.                 min = arr[j]; // 重置min
  34.                 minIndex = j; // 重置minIndex
  35.             }
  36.         }
  38.         // 将最小值，放在arr[0], 即交换
  39.         if(minIndex != 1) {
  40.             arr[minIndex] = arr[1];
  41.             arr[1] = min;
  42.         }
  44.         System.out.println("第2轮后~~");
  45.         System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
  47.         //第3轮
  48.         minIndex = 2;
  49.         min = arr[2];
  50.         for (int j = 2 + 1; j < arr.length; j++) {
  51.             if (min > arr[j]) { // 说明假定的最小值，并不是最小
  52.                 min = arr[j]; // 重置min
  53.                 minIndex = j; // 重置minIndex
  54.             }
  55.         }
  57.         // 将最小值，放在arr[0], 即交换
  58.         if (minIndex != 2) {
  59.             arr[minIndex] = arr[2];
  60.             arr[2] = min;
  61.         }
  63.         System.out.println("第3轮后~~");
  64.         System.out.println(Arrays.toString(arr));// 1, 34, 101, 119 */

运行截图
image.png

代码2

  3.     public static void selectionSort(int[] array) {
  4.         if (array == null || array.length <= 1) {
  5.             return;
  6.         }
  8.         int length = array.length;
  9.         for (int i = 0; i < length - 1; i++) {
  10.             // 保存最小数的索引
  11.             int minIndex = i;
  13.             for (int j = i + 1; j < length; j++) {
  14.                 // 找到最小的数
  15.                 if (array[j] < array[minIndex]) {
  16.                     minIndex = j;
  17.                 }
  18.             }
  19.             // 交换元素位置
  20.             if (i != minIndex) {
  21.                 swap(array, minIndex, i);
  22.             }
  23.         }
  25.     }
  27.     private static void swap(int[] array, int a, int b) {
  28.         int temp = array[a];
  29.         array[a] = array[b];
  30.         array[b] = temp;
  31.     }
  32. }

5.选择排序与冒泡排序的比较

  1. 时间负责度都是O（n2）
  2. 空间复杂度都是O（1）
  3. 选择排序是从第一位开始确定最大或最小的数，保证前面的数都是有序的，且都比后面的数小或大；

冒泡排序是从最后一位开始确定最大或最小的数，保证后面的数都是有序的且都大于或小于前面的数。