【排序算法】2.选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置

java 实现：

public class ChooseOrderTest {
    public static void main(String[] args) {
        int[] input = new int[]{2,5,4,89,7,89,52,12,54,78};
        for (int n = 0; n < input.length; n++){
            int minIndex = n;
            for (int m = n; m < input.length; m++){
                if (input[m] < input[minIndex]){
                    minIndex = m;
                }
            }
            if(minIndex != n){
                int temp = input[minIndex];
                input[minIndex] = input[n];
                input[n] = temp;
            }
        }
        PrintUtils.print(input);
    }
}

时间复杂度

• 最优时间复杂度：O(n^2)
  （和冒泡不同，每次循环，未排序的部分都可能是乱序，所以无法判断何时跳出，例如：1 2 3 4 5, 排到 3，实际上已经完成排序了，但是选择排序无法知道，后面的排序是正确的，仍要走完循环才行）
• 最坏时间复杂度：O(n^2)
• 稳定性：不稳定（不稳定发生在最小元素与 input[i] 交换的时刻，例如：在取最大值优先等情况下，3 2 8 8 5 的排序为 2 3 5 8 8，可以看到两个 8 颠倒了顺序）

相比于冒泡排序，选择排序更划算，因为冒泡需要不断地交换，而选择排序则是比较一轮，然后再进行交换一次。通常情况交换次数要少于冒泡排序。