思路
例如有如下数组：
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方级别的算法复杂度分析
