一般的选择排序

public void selectionSort(int[] a) {
    int minIndex;    // 记录每一轮的最小值索引
    for (int i = 0; i < a.length - 1; i++) {
        // 选出最小值赋给 a[i]，a[i] 前面的数都已排好序
        minIndex = i;
        for (int j = i+1; j < a.length; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(a, i, minIndex);
        }
    }
}

其中 swap 方法用于交换数组元素：

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

一共进行 n-1 轮，每轮都确定一个最小的数（也可以是最大的），记录下最小数的索引，最后再和开头的数交换。

选择排序比起冒泡排序，优化的地方在于减少了交换次数。冒泡排序在一轮中元素可能要交换多次，而选择排序只是比较元素，先记录下最小（大）值，等到一轮遍历完成后才进行交换（如果需要的话）。

当前，交换的次数是减少了，但有时也会增加比较的次数。因为选择排序需要进行的轮次是固定的，不能像冒泡排序那样提取结束。

选择排序的优化

其中一个优化思路是：每一轮遍历分别选出最大值和最小值的索引，可以减少遍历轮次。

public void selectionSort_b(int[] a) {
    int left = 0;
    int right = a.length - 1;
    int minIndex;    // 记录每一轮的最小值索引
    int maxIndex;   // 记录每一轮的最大值索引
    while (left < right) {
        minIndex = left;
        maxIndex = left;
        for (int i = left+1; i <= right; i++) {
            if (a[i] < a[minIndex]) {
                minIndex = i;
            }
            if (a[i] > a[maxIndex]) {
                maxIndex = i;
            }
        }
        if (minIndex == maxIndex) { // 说明剩下的所有值都相等，无需再交换
            break;
        }
        // 剩下的数中，保证 a[left] 最小，a[right] 最大
        if (left != minIndex) {
            swap(a, left, minIndex);
        }
        // 注意：left == maxIndex 的情况需要进行特殊处理
        // 因为经过上面的 if 后，原来的 a[left] 已经交换到了 a[minIndex] 处，
        // 所有如果 left 是 maxIndex 的话，就需要更新一下 maxIndex
        if (maxIndex == left) {
            maxIndex = minIndex;
        }
        if (right != maxIndex) {
            swap(a, right, maxIndex);
        }
        // 更新边界
        left++;
        right--;
    }
}

在遍历完后进行交换时，需要注意索引的更新：

if (left != minIndex) {
    swap(a, left, minIndex);
}
// 注意：left == maxIndex 的情况需要进行特殊处理
// 因为经过上面的 if 后，原来的 a[left] 已经交换到了 a[minIndex] 处，
// 所有如果 left 是 maxIndex 的话，就需要更新一下 maxIndex
if (maxIndex == left) {
    maxIndex = minIndex;
}
if (right != maxIndex) {
    swap(a, right, maxIndex);
}

留意中间那个 if，如果 maxIndex == left，那么在 left 处的最大值可能已经被换到 minIndex 处了（在第一个 if 处被换掉），所以要记得更新 maxIndex。

例如对于数组 [10,5,0,6,4]，假设此时 left = 0、right = 4，循环一次后，得到 minIndex = 2, maxIndex = 0。

首先将 left 和 minIndex 位置的元素交换，得到数组 [0,5,10,6,4]。

明显现在的最大值的索引已经变成 2 了，但 maxIndex 还是 0，如果不更新 maxIndex 的话，最终的结果就是 [4,5,10,6,0]，显然这是错误的。

选择排序及其优化

一般的选择排序

选择排序的优化

参考