选择排序

选择排序是一种简单直观的排序算法，无论什么数据都是O(n^2)的时间复杂度。所以用到它的时候，数据规模越小越好。

算法步骤

1. 从数组中找出最小的那个元素，然后与最开始的元素交换位置
2. 忽略第一步中找到的最小元素，重复执行步骤1

动图演示

算法实现

for (int i = 0; i < array.length - 1; i++) {
    int minIndex = i; // 保存最小元素索引
    for (int j = i; j < array.length; j++) {
        if(cmp(minIndex, j) > 0) {
            minIndex = j;
        }
    }
    swap(i, minIndex); // 将最小元素交换到开始位置
}

也可以挑选出最大元素，与最后的元素的交换，实现代码如下：

for (int end = array.length - 1; end > 0; end--) {

    int maxIndex = 0; // 记录最大索引
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(maxIndex, begin) <= 0) {
            maxIndex = begin;
        }
    }
    swap(maxIndex, end); // 将最大元素交换到最后位置
}

选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序。

最好、最坏、平均时间复杂度：O(n^2)。

空间复杂度：O(1)。

选择排序是一个不稳定的排序算法，看下面的例子：

• 排序前：5* 5 1 7
• 排序后：1 5 5* 7

算法优化

选择排序每次循环中都需要找出最小（大）的元素与开始（最后）位置的元素进行交换，可以使用大顶堆来实现查找最大元素，可以将查找元素的时间复杂度由O(n)降低为O(logn)，其实就是堆排序。

更多精彩内容关注本人公众号：架构师升级之路