2.选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。**

1.算法步骤（n个数据升序）：

1）第一轮：从第一位开始，找到最小的数和第一位换位置
2）第二轮：从第二位开始，找到最小的数和第二位换位置
3）……
……
n-1）第n-1轮：从n-1开始，和第n个数比较大小，更小的放在n-1位置
其实选择排序和冒泡排序很相似，不同的是：
冒泡排序每次比较都需要把更大的往后挪一位，一步一步往下沉，
选择排序每次比较只是找到最值，不会马上换位置，一轮结束才更换位置。

2.动图演示

3.代码实现

public class SelectionSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }
            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
        return arr;
    }
}