选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

通俗的解释

　　它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

时间复杂度

步数约为N^2的一半,大O记法忽略常数,为O(N^2）

选择排序的步骤

（1）从左至右检查数组的每个格子，找出值最小的那个。在此过程中，我们会用一个变量来记住检查过的数字的最小值（事实上记住的是索引，但为了看起来方便，下图就直接写出数值）。如果一个格子中的数字比记录的最小值还要小，就把变量改成该格子的索引，如图所示。

（2）知道哪个格子的值最小之后，将该格与本次检查的起点交换。第1次检查的起点是索引0，第2次是索引1，以此类推。下图展示的是第一次检查后的交换动作。

（3）重复第（1）（2）步，直至数组排好序。

java示例:

public static void selectSort(Integer[] a) {
    int minIndex = 0;
    int temp = 0;
    for (int i = 0; i < a.length - 1; i++) {
        minIndex = i;//无序区的最小数据数组下标
        for (int j = i + 1; j < a.length; j++) {
            //在无序区中找到最小数据并保存其数组下标
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        //将最小元素放到本次循环的前端
        temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }
}

public static void main(String[] args) {
    Integer[] myList = { 5, 3, 6, 2, 10 };
    selectSort(myList); //{2, 3, 5, 6, 10}

    for (Integer integer : myList) {
        System.out.println(integer);
    }
}

js示例:

function selectionSort(array){
  for(var i=0; i < array.length; i++){//这个外层的循环代表每一轮检查。在一轮检查之初，我们会先记住目前的最小值的索引。 
    var lowestNumberIndex=i;//因此每轮开始时lowestNumberIndex都会是该轮的起点索引i。    
    for(var j=i+1; j < array.length; j++){//此行代码发起一个以i+1开始的内层循环。    
      if(array[j] < array[lowestNumberIndex]){//循环内逐个检查数组未排序的格子，若遇到比之前记录的本轮最小值还小的格子值     
        lowestNumberIndex=j;//就将lowestNumberIndex更新为该格子的索引。      
      }    
    }
    //内层循环结束时，会得到未排序数值中最小值的索引。    
    if(lowestNumberIndex != i){//然后再看看这个最小值是否已在正确位置，即该索引是否等于i。如果不是，就将i所指的值与最小值交换。    
      var temp=array[i];      
      array[i]=array[lowestNumberIndex];      
      array[lowestNumberIndex]=temp;  
    }
  }  
  return array;
}

参考:https://baike.baidu.com/item/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F

参考:数据结构与算法图解.5