排序：选择排序

思路

例如有如下数组：

image.png

对于选择排序来讲，它假定数组分两部分，前一部分是已排序的元素，后一部分是未排序的元素。每次循环的任务，就是从未排序部分找出一个最小的元素，将其放到未排序部分的最前面，已排好序部分元素增加一个，直至所有元素排序完成。
对于上面数组来讲，假定已经排序好两个元素：

image.png

那么接下来，就是寻找绿色部分最小的元素（用minIndex标记），然后和i处的元素进行交换即可：

image.png

交换后为：

image.png

因此，这个算法的循环不变量为：data[0 ... i)的元素都已排好序，data[i ... data.length)未排序。

int实现

public static void sort(int[] data) {
    for (int i = 0; i < data.length; i++) {
        // 这个循环体的作用是维持循环不变量data[0 ... i)都是已排序的
        int minIndex = i;
        for (int j = i; j < data.length; j++) {
            // 这个循环体的作用是寻找最小元素的坐标
            if (data[j] < data[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(data, i, minIndex);
        }
    }
}
private static void swap(int[] data, int i, int j) {
    int t = data[i];
    data[j] = data[i];
    data[i] = t;
}

范型实现

public static <E extends Comparable<E>> void sort(E[] data) {
    for (int i = 0; i < data.length; i++) {
        // 这个循环体的作用是维持循环不变量data[0 ... i)都是已排序的
        int minIndex = i;
        for (int j = i; j < data.length; j++) {
            // 这个循环体的作用是寻找最小元素的坐标
            if (data[j].compareTo(data[minIndex]) < 0) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(data, i, minIndex);
        }
    }
}
private static <E> void swap(E[] data, int i, int j) {
    E t = data[i];
    data[j] = data[i];
    data[i] = t;
}

时间复杂度分析

对于选择排序来讲，两重循环的遍历，因此时间复杂度为O(n^2)

算法测试

public static void testSort(String sortName) {
    int[] dataSize = {1000, 10000, 100000};
    for (int len : dataSize) {
        Integer[] data = ArrayGenerator.generateRandomIntArray(len, len);
        long startTime = System.currentTimeMillis();
        if (sortName.equals(SelectionSort.class.getSimpleName())) {
            SelectionSort.sort(data);
        }
        long costTime = System.currentTimeMillis() - startTime;
        if (!isSorted(data)) {
            throw new RuntimeException(sortName + " sort failed");
        }
        System.out.println(String.format("%s: n = %d, costTime: %fS", sortName, len, costTime / 1000.0f));
    }
}

测试结果为：

SelectionSort: n = 1000, costTime: 0.006000S
SelectionSort: n = 10000, costTime: 0.111000S
SelectionSort: n = 100000, costTime: 9.039000S

结果大致符合n方级别的算法复杂度分析