选择排序

这是一个比较直观的，最简单的排序算法，大致是这样的：首先找到数组中最小的那个元素，然后，将它和数组的第一个元素交换位置（如果第一个元素已经是最小的，那么它就和自己交换）。接着，在剩下的元素中找到最小元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这就是选择排序。

简单实现如下：

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）次，复杂度大大增加了。