介绍

选择排序和冒泡排序的算法其实都比较好理解，都是从大到小（从小到大）操作的排序，冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

时间复杂度：

• 最好情况：O(n^2)
• 平均情况：O(n^2)
• 最坏情况：O(n^2)

稳定性：不稳定

额外的空间：O(1)

过程

1. 在序列中找到最小（大）元素，放到起始位置作为已排序序列；
2. 从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾；
3. 以此类推，直到所有元素均排序完毕；

图示：

宏观过程：

Java实现

/*
 * SelectionSort.java:选择排序
 */

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        int[] a = new int[]{9, 2, 5, 6, 7, 2, 4, 5};
        System.out.println(Arrays.toString(sort(a)));
    }

    private static int[] sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int min = i;
            //从i开始遍历数组找到最小值索引
            for (int j = i; j < a.length; j++){
                if (a[j] < a[min]) {
                    min = j;//记录索引
                }
            }
            //交换最小值，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
            if (min != i) {
                int temp = a[i];
                a[i] = a[min];
                a[min] = temp;
            }
        }
        return a;
    }
}