排序演算法入門之「選擇排序」-有解無憂

選擇排序

選擇排序也是利用了“擋板法”這個經典思想，

擋板左邊是已排序區間，右邊是未排序區間，那么每次的“選擇”是去找右邊未排序區間的最小值，找到之后和擋板后面的第一個值換一下，然后再把擋板往右移動一位，保證排好序的這些元素在擋板的左邊，

比如之前的例子：{5, 2, 0, 1}

我們用一個擋板來分隔陣列是否排好序，用指標 j 來尋找未排序區間的最小值；

第一輪 j 最初指向 5，然后遍歷整個未排序區間，最終指向 0，那么 0 就和擋板后的第一個元素換一下，也就是和 5 交換一下位置，擋板向右移動一位，結束第一輪，

第二輪，j 從擋板后的2開始遍歷，最終指向1，然后1和擋板后的第一個元素 2 換一下，擋板向右移動一位，結束第二輪，

第三輪，j 從2開始遍歷，最終指向2，然后和2自己換一下，擋板向右移動一位，結束第三輪，

還剩一個元素，不用遍歷了，就結束了，

選擇排序與之前的插入排序對比來看，要注意兩點：

擋板必須從 0 開始，而不能從 1 開始，雖然在這兩種演算法中，擋板的物理意義都是分隔已排序和未排序區間，但是它們的已排序區間里放的元素的意義不同：

選擇排序是只能把當前的最小值放進來，而不能放其他的；
插入排序的第一個元素可以為任意值，

所以選擇排序的擋板左邊最開始不能有任何元素，

在外層回圈時，

選擇排序的最后一輪可以省略，因為只剩下最大的那個元素了；
插入排序的最后一輪不可省略，因為它的位置還沒定呢，

class Solution {
 public void selectionSort(int[] input) {
  if(input == null || input.length <= 1) {
   return;
  } 
  for(int i = 0; i < input.length - 1; i++) {
   int minValueIndex = i;
   for(int j = i + 1; j < input.length; j++) {
    if(input[j] < input[minValueIndex]) {
     minValueIndex = j;
    }
   }
   swap(input, minValueIndex, i);
  }
 }
 private void swap(int[] input, int x, int y) {
  int tmp = input[x];
  input[x] = input[y];
  input[y] = tmp;
 }
}