引言

上篇文章中我们分析了冒泡排序，我们知道了冒泡排序可能需要N-1次交换和N-1次比较。
N-1次比较在所难免，但N-1次交换是必须的么？
今天我们介绍的选择排序方法只需要一次交换。

思路

思路也很简单：每趟从待排序的序列中选择最小的元素，放到已排序序列末尾；

这里通过交换实现原地排序。

我们对该序列进行排序：

是不是和冒泡排序很相似，左边橙色部分是已排序序列，右边是待排序序列，且右边必不小于左边。
并且，可以看到：2、3、7趟并没有发生交换。

代码

/**
 * 每趟排序从i右边找到最小的元素，和i交换(选择)
 * @param a
 * @param <E>
 */
public static <E extends Comparable<? super E>> void selectionSort(E[] a) {
    for (int i = 0; i < a.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < a.length ; j++) {
            //找到右边最小元素索引
            if (a[j].compareTo(a[minIndex]) < 0) {
                minIndex = j;
            }
        }
        swap(a,i,minIndex);
        //System.out.println("i=" + i + Arrays.toString(a));
    }
}

private static <E> void swap(E[] array, int i, int j) {
    if (i == j) return;
    E tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

复杂度和稳定性

• 时间复杂度

最坏情况下是$\Theta(N^2)$Θ(N2)

• 稳定性

简单选择排序由于选出最小值后需要交换位置,位置一变就会变得不稳定。
例如序列5 8 5 2 9， 我们知道第一遍，第一个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法