冒泡排序：在每一次比较的时候，如果发现相邻两数的次序不对，都会马上就把两数进行对调。

选择排序：则在比较过程中（内循环里面）并不进行对调，而是先记录下最小（大）数的下标，在一次扫描完成后再进行对调。 

1、算法思想

在要排序的一组数中，选出最小（或者最大）的一个数与第 i（i=0）个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第i+1个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

2、代码实现

  /**
     * 在要排序的一组数中，选出最小（或者最大）的一个数与第 i（i=0）个位置的数交换； 然后在剩下的数当中再找最小（或者最大）的与第i+1个位置的数交换， 依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
     */
    private static void SimpleSelectSort(int[] source) {
        if (source.length <= 1 || source == null) {// 习惯，参数判断
            return;
        }
        for (int i = 0; i < source.length - 1; i++) { // i < source.length尚可
            int j = i + 1;
            int min = source[i]; // 最小值
            int minIndex = i; // 最小值下标
            while (j < source.length) {
                if (source[j] < min) {
                    min = source[j];
                    minIndex = j;
                }
                j++;
            }
            if (minIndex != i) { // 3次赋值
                source[i] = source[minIndex] + (source[minIndex] = source[i]) * 0;
            }
            printArr(source);
        }
    }

3、算法分析

1.时间复杂度

选择排序的交换操作介于 0 和 (n - 1）次之间。

选择排序的比较操作为 n (n - 1）/ 2次。

选择排序的赋值操作介于 0 和 3 (n - 1）次之间(n-1次交换，每次交换需要赋值3次) t = a, a = b, b = t。

比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。

交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。

交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

2.稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

4、算法改进

二元选择排序

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：（类冒泡）

/**
     * 简单选择排序，每趟循环只能确定一个元素排序后的定位。 我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置。 从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。
     */
    private static void TwoSelectSort(int[] source) {
        int n = source.length;
        if (n <= 1 || source == null) {// 习惯，参数判断
            return;
        }
        int minIndex, maxIndex, tempI;
        for (int i = 0; i < n / 2; i++) {
            minIndex = maxIndex = i;
            for (int j = i + 1; j < n - i; j++) {
                if (source[j] < source[minIndex]) {
                    minIndex = j;
                    continue;
                }
                if (source[j] > source[maxIndex]) {
                    maxIndex = j;
                }
            }
            if (minIndex != i) { // 3次赋值
                source[i] = source[minIndex] + (source[minIndex] = source[i]) * 0;
            }
            if (maxIndex == i) { // 此时最大值已被替换到minIndex处
                maxIndex = minIndex;
            }
            if (maxIndex != n - i - 1) {
                source[n - i - 1] = source[maxIndex] + (source[maxIndex] = source[n - i - 1]) * 0;
            }
            printArr(source);
        }
    }

冒泡排序改进算法之每趟循环确定两个元素时，不用考虑 if（maxIndex==i），因为其每趟比较只要不符合排序就要交换位置，而不是仅仅记录其索引的改变。

源码地址：https://github.com/zxiaofan/Algorithm/blob/master/src/sort/SelectSort.java