转载声明：文章来源 https://blog.csdn.net/u022812849/article/details/106985668

选择排序
选择排序是一种简单直观的排序算法，无论什么数据都是O(n^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)，其实就是堆排序。