八大排序算法之选择排序

时间复杂度：O(N^2)
额外空间复杂度：O(1)
是否可实现稳定性：否

思路：

初始化一个变量minIndex用来存储最小数值的下标，每次循环找出最小下标minIndex，然后和当前外层循环最前面的数交换，就能做到每次把本次循环中的最小数值放到最前面

例子：

比如一组数{2，5，1，9}
每次初始化minIndex为当前外循环的最前面的数字，第一次minIndex=0
比较2和5，2<5所以minIndex值不变，再比较2和1，2>1所以minIndex的值变成2
再比较1和9，1<9，minIndex不变，此时所有数值比较完毕，然后交换minIndex和i的值，i代表外层循环的位置
第二次循环，minIndex=1，过程和第一次一样，依次执行下去得到结果

代码：

 public static void selectionSort(int[] arr){
      if (arr==null||arr.length<2){
          return;
      }
      
      /*
      * 选择排序的思想： 遍历数组  初始化一个变量，代表每次循环找到的最小的数的下标
      * 内循环，每一次找的都是最小数的下标，然后每次用当前最小下标的元素和arr[j]比较，
      * 看看当前的下表是否是最小下标 循环结束，minIndex就是这一次循环找到的最小的数的下标
      * 然后交换i和minIndex的下标
      * i代表每次开始的位置也就是每次循环最小的位置
      **/
      for (int i = 0;i<arr.length;i++){
          int minIndex = i;
          for (int j = i+1;j<arr.length;j++){
              minIndex = arr[minIndex] < arr[j]?minIndex:j;
          }
          swap(arr,i,minIndex);
      }
  }

    public static void swap(int[]arr,int i ,int j){
        int temp = 0;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

在这里注意，选择排序是不稳定的，举个例子序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了。