选择排序
这是一个比较直观的，最简单的排序算法，大致是这样的：首先找到数组中最小的那个元素，然后，将它和数组的第一个元素交换位置（如果第一个元素已经是最小的，那么它就和自己交换）。接着，在剩下的元素中找到最小元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这就是选择排序。
简单实现如下：
public static void main(String[] args) {
int[] arr = {5, 1, 7, 3, 0, 8, 2, 6, 4, 9};
int N = arr.length;
for(int i=0; i<N; i++) {
int min = i;
for(int j=i+1; j<N; j++) {
if(arr[min] > arr[j]) {
min = j;
}
}
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
for(int n=0; n<N; n++) {
System.out.println(arr[n] + " ");
}
}
选择排序很容易误写成另外的样子：
public static void main(String[] args) {
int[] arr = {5, 1, 7, 3, 0, 8, 2, 6, 4, 9};
int N = arr.length;
for(int i=0; i<N; i++) {
for(int j=i+1; j<N; j++) {
if(arr[i] > arr[j]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
for(int n=0; n<N; n++) {
System.out.println(arr[n] + " ");
}
}
真正的选择排序，每次找出一个最小值，然后交换位置，最终完成排序，需要交换N次。而上面的代码，每次比较如果数组前面的大于后面的就交换位置，实际上交换次数变为了（(N-1) + (N-2) +...+1）次，复杂度大大增加了。
