选择排序算法也是可以优化的，既然每轮遍历时找出了最小值，何不把最大值也顺便找出来呢？这就是二元选择排序的思想。

使用二元选择排序，每轮选择时记录最小值和最大值，可以把数组需要遍历的范围缩小一倍。

public static void selectionSort2(int[] arr) {
    int minIndex, maxIndex;
    // i 只需要遍历一半
    for (int i = 0; i < arr.length / 2; i++) {
        minIndex = i;
        maxIndex = i;
        for (int j = i + 1; j < arr.length - i; j++) {
            if (arr[minIndex] > arr[j]) {
                // 记录最小值的下标
                minIndex = j;
            }
            if (arr[maxIndex] < arr[j]) {
                // 记录最大值的下标
                maxIndex = j;
            }
        }
        // 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 arr[i] 相等，此时已经排序完成
        if (minIndex == maxIndex) break;
        // 将最小元素交换至首位
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
        // 如果最大值的下标刚好是 i，由于 arr[i] 和 arr[minIndex] 已经交换了，所以这里要更新 maxIndex 的值。
        if (maxIndex == i) maxIndex = minIndex;
        // 将最大元素交换至末尾
        int lastIndex = arr.length - 1 - i;
        temp = arr[lastIndex];
        arr[lastIndex] = arr[maxIndex];
        arr[maxIndex] = temp;
    }
}

我们使用 记录最小值的下标， 记录最大值的下标。每次遍历后，将最小值交换到首位，最大值交换到末尾，就完成了排序。

由于每一轮遍历可以排好两个数字，所以最外层的遍历只需遍历一半即可。

二元选择排序中有一句很重要的代码，它位于交换最小值和交换最大值的代码中间：

if (maxIndex == i) maxIndex = minIndex;

这行代码的作用处理了一种特殊情况：如果最大值的下标等于 i，也就是说 arr[i] 就是最大值，由于 arr[i] 是当前遍历轮次的首位，它已经和 arr[] 交换了，所以最大值的下标需要跟踪到 arr[i] 最新的下标 。

二元选择排序的效率

在二元选择排序算法中，数组需要遍历的范围缩小了一倍。那么这样可以使选择排序的效率提升一倍吗？

从代码可以看出，虽然二元选择排序最外层的遍历范围缩小了，但 for 循环内做的事情翻了一倍。也就是说二元选择排序无法将选择排序的效率提升一倍。但实测会发现二元选择排序的速度确实比选择排序的速度快一点点，它的速度提升主要是因为两点：

在选择排序的外层 for 循环中，i 需要加到 arr. - 1 ，二元选择排序中 i 只需要加到 arr. / 2

在选择排序的内层 for 循环中，j 需要加到 arr. ，二元选择排序中 j 只需要加到 arr. - i

我们不妨发扬一下极客精神，一起来做一个统计实验：

public class TestSelectionSort {
    public static void selectionSort(int[] arr) {
        int countI = 0;
        int countJ = 0;
        int countArr = 0;
        int minIndex;
        countI++;
        for (int i = 0; i < arr.length - 1; i++, countI++) {
            minIndex = i;
            countJ++;
            for (int j = i + 1; j < arr.length; j++, countJ++) {
                if (arr[minIndex] > arr[j]) {
                    // 记录最小值的下标
                    minIndex = j;
                }
                countArr++;
            }
            // 将最小元素交换至首位
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        int count = countI + countJ + countArr;
        System.out.println("selectionSort: countI = " + countI + ", countJ = " + countJ + ", countArr = " + countArr + ", count = " + count);
    }
    public static void selectionSort2(int[] arr) {
        int countI = 0;
        int countJ = 0;
        int countArr = 0;
        int minIndex, maxIndex;
        countI++;
        // i 只需要遍历一半
        for (int i = 0; i < arr.length / 2; i++, countI++) {
            minIndex = i;
            maxIndex = i;
            countJ++;
            for (int j = i + 1; j < arr.length - i; j++, countJ++) {
                if (arr[minIndex] > arr[j]) {
                    // 记录最小值的下标
                    minIndex = j;
                }
                if (arr[maxIndex] < arr[j]) {
                    // 记录最大值的下标
                    maxIndex = j;
                }
                countArr += 2;
            }
            // 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 arr[i] 相等，此时已经排序完成
            if (minIndex == maxIndex) break;
            // 将最小元素交换至首位
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
            // 如果最大值的下标刚好是 i，由于 arr[i] 和 arr[minIndex] 已经交换了，所以这里要更新 maxIndex 的值。
            if (maxIndex == i) maxIndex = minIndex;
            // 将最大元素交换至末尾
            int lastIndex = arr.length - 1 - i;
            temp = arr[lastIndex];
            arr[lastIndex] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
        int count = countI + countJ + countArr;
        System.out.println("selectionSort2: countI = " + countI + ", countJ = " + countJ + ", countArr = " + countArr + ", count = " + count);
    }
}

在这个类中，我们用 记录 i 的比较次数， 记录 j 的比较次数， 记录 arr 的比较次数，count 记录总比较次数。

测试用例：

import org.junit.Test;
import java.util.ArrayList;
public class UnitTest {
    @Test
    public void test() {
        ArrayList list = new ArrayList<>();
        for (int i = 0; i <= 1000; i++) {
            // ArrayList 转 int[]
            int[] arr = list.stream().mapToInt(Integer::intValue).toArray();
            System.out.println("*** arr.length = " + arr.length + " ***");
            TestSelectionSort.selectionSort(arr);
            TestSelectionSort.selectionSort2(arr);
            list.add(i);
        }
    }
}

这里列出部分测试结果，感兴趣的读者可以自己运行此测试用例验证：

数组长度排序算法i 比较次数j 比较次数数组元素比较次数总比较次数

选择排序

二元选择排序

选择排序

二元选择排序

选择排序

二元选择排序

选择排序

11

二元选择排序

10

选择排序

10

54

45

109

10

二元选择排序

30

50

86

100

选择排序

100

5049

4950

10099

100

二元选择排序

51

2550

5000

7601

1000

选择排序

1000

1000

二元选择排序

501

可以看到，二元选择排序中， arr 数组的比较次数甚至略高于选择排序的比较次数，整体是相差无几的。只是 i 和 j 的比较次数较少，正是在这两个地方提高了效率。

并且，在二元选择排序中，我们可以做一个剪枝优化，当 == 时，说明后续所有的元素都相等，就好比班上最高的学生和最矮的学生一样高，说明整个班上的人身高都相同了。此时已经排序完成，可以提前跳出循环。通过这个剪枝优化，对于相同元素较多的数组，二元选择排序的效率将远远超过选择排序。

和选择排序一样，二元选择排序也是不稳定的。

时间复杂度 & 空间复杂度

前文已经说到，选择排序使用两层循环，时间复杂度为O(n^2); 只使用有限个变量，空间复杂度O(1)。二元选择排序虽然比选择排序要快，但治标不治本，二元选择排序中做的优化无法改变其时间复杂度，二元选择排序的时间复杂度仍然是O(n^2)；只使用有限个变量，空间复杂度O(1)。