选择排序 --- Java版

思路

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

［17,3,25,14,20,9］.png

代码

因为思路比较简单所以直接写出代码:

public class SelectionSort {

    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;              //min初始值都是为第一趟遍历的元素下标
            for (int j = i + 1; j < N; j++)
                if (less(a, j, min)) // 需要更新min的值
                    min = j;
            swap(a, i, min);
        }
    }

    private static boolean less(Comparable[] a, int i, int j) {
        if (a[i].compareTo(a[j]) < 0)
            return true;
        else
            return false;
    }

    private static void swap(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

性能

接下来分析下选择排序的复杂度。每次外层遍历的元素a[i]，都会有a[j]会与之比较,并且j是自增到数组最后一个元素, 所以这个算法至少需要(N– 1) + (N– 2) + ... + 1 + 0 ＝ N^2 / 2 次比较，并且每个外层循环i都会有一次swap交换所以至少需要N次交换。

algorithm4_princeton.png

如果数组是['S', 'O', 'R', 'T', 'E', 'X', 'A', 'M', 'P', 'L', 'E']。那么根据上图按照程序执行每一步以后可以发现灰色区域是有序区，黑色是待排无序区。正好发现他们面积各占1/2。这就是该算法N^2 / 2 次比较的物理表现。
  所以选择排序时间复杂度是O(N^2),空间复杂度是O(1)。而且我们还会发现即使原来数组以及排好顺序了调用这个算法依然需要O(N^2)时间复杂度。最好，最坏，平均情况：都为O(n^2),并且还是不稳定排序算法。(稳定性这里不展开了,自己试验下就行了)。