本文将介绍两类选择排序：简单选择排序、二元选择排序的思路，以及探讨在算法实现中可能出现的问题。

选择排序在运行中使数组分为有序区和无序区两部分

简单选择排序（升序）

左侧有序区

public static void selectMinToFront(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) min = j;
        }
        int t = a[i]; 
        a[i] = a[min]; 
        a[min] = t;
    }
}

外层循环

范围：0 ~ n-1 一共n-1轮

终止：枚举到倒数第二个下标 最后一位不需要再进行处理

内层循环

范围：i+1 ~ n-1 起点是外层循环i往后一位（无序区第二位 暂时保留第一位） 终点是数组最后一位

终止：枚举到数组最后一位

每一次外层循环都代表着开启一轮新的内层循环

内层循环开始前创建临时变量min，用以储存当前内层循环遍历到的最小值下标，并且假定新一轮循环得到的最小值为无序区的第一位。

内层循环遍历其余无序区，寻找最小值并记录下标。

将无序区第一位 i 的值与，刚才找到的最小值进行对调。

简易视图

我们假定有序区为A 无序区为B 数组长度 n

现在对含有五个元素的数组进行排序，有序区和无序区的变化如下图所示：

[ B B B B B ] 原始数组
-- 开始外层循环 --
第1轮 i=0: [ A B B B B ]
第2轮 i=1: [ A A B B B ]
第3轮 i=2: [ A A A B B ]
第4轮 i=3: [ A A A A B ] 结束（总共 n-1 轮）

右侧有序区

public static void selectMaxToBack(int[] a) {
    int n = a.length;
    for (int end = n - 1; end > 0; end--) {
        int max = 0;
        for (int j = 1; j <= end; j++) {
            if (a[j] > a[max]) max = j;
        }
        int t = a[end]; a[end] = a[max]; a[max] = t;
    }
}

基本思路同上述左侧有序区一致，仅调转执行逻辑，变更为从右向左查找最大值。

二元选择排序（升序）

public static void selectMinMaxBothEnds(int[] a) {
    int left = 0, right = a.length - 1;
    while (left < right) {
        int min = left, max = left;
        for (int j = left; j <= right; j++) {
            if (a[j] < a[min]) min = j;
            if (a[j] > a[max]) max = j;
        }

        // 先把最小放到 left
        int t = a[left]; a[left] = a[min]; a[min] = t;

        // 如果最大值原来在 left，被换走了，要修正 max 的位置
        if (max == left) max = min;

        // 再把最大放到 right
        t = a[right]; a[right] = a[max]; a[max] = t;

        left++;
        right--;
    }
}

首先创建left 和 right两个下标变量 用来锚定无序区边界

外层while循环

循环条件：左右边界不重合

每一次循环都会创建最大最小值下标变量，并且默认无序区左边界left位置既是最小候选也是最大候选（min=max=left）

内层for循环

范围：left ~ right

在无序区寻找最大和最小值 把最小值放在left 最大值放在right。

处理特殊情况

因为我们先替换最小值到left，如果最大值在left那么就会导致最小值被交换到left，最大值被换到别处。

因此需要把最大值暂存到数组中找到的最小值的位置。

我们需要更改最大值下标到循环查找到的最小值下标，把这种情况下出现的最大值给到right。

最后向中心收缩无序区 并开启下一轮循环

首图图片来源：菜鸟教程（侵删）