简单选择排序（Selection Sort） O(n^2) 不稳定

介绍

简单选择排序是一种选择排序，核心思想是在无序的数列中找到最小的值放入有序序列中，直到所有元素排序完成。

算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，R[1..i]为有序序列，R[i+1..n)无序序列；
• n-1趟结束，数组有序化了。

稳定性

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

动图展示

selectionSort.gif

代码实现

public class SelectionSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{27, 6, 27, 42, 23, 15, 38, 50, 35, 14, 40, 28, 29};
        print(arrays);
        int[] res = selectionSort(arrays);
        print(res);
    }

    private static int[] selectionSort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;
            for (int j = i; j < arr.length; j++) {
                minIdx = arr[j] < arr[minIdx] ? j : minIdx;
            }
            swap(arr, i, minIdx);
        }
        return arr;
    }

    private static void swap(int[] arr, int i, int j) {
        if (i != j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}