选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
/**
* 选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。
* 但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。
* 举个栗子，对 5,3,8,6,4 这个无序序列进行简单选择排序，
* 首先要选择 5 以外的最小数来和 5 交换，也就是选择 3 和 5 交换，一次排序后就变成了 3,5,8,6,4.
* 对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。
* 其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。
* 选择排序的时间复杂度为 O(n^2)
*
* @author wb
*/
public class SelectSort {
public static void selectSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
int minIndex;
for (int i = 0; i < arr.length - 1; i++) { //只需要比较n-1次
minIndex = i;
//从i+1开始比较，因为minIndex默认为i了，i就没必要比了。
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { //如果minIndex不为i，说明找到了更小的值，交换之。
swap(arr, i, minIndex);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
白话分析：
- 从第一个元素循环遍历每一个元素，找到最小的元素，遍历一轮结束后和第一个元素进行交换，此时最小值处于数组前面；
- 重复步骤一，遍历剩余的序列；
- 每一轮完毕后剩余队列最小者都会被交换到最左侧；
- 最终得到一个有序队列；
选择排序.gif
