/**
 * 选择排序
 * 步骤：
 *  1、用i标识将数组分为排好序和未排序两部分
 *  2、遍历未排序部分，将最小值和未排序的第一个替换位置，然后i+1，后面继续循环遍历
 * 时间复杂度：n^2
 */
public class SelectionTest {
    public static void main(String[] args) {
        int[] arr = {3,1,6,3,8,3,5,9,4,67,2,5,7,2,6,3,5};
        selectionSort(arr);
        for (int i : arr) {
            System.out.print(i+",");
        }
    }

    /**
     * 选择排序：遍历找最小值往前面填
     *
     * @param arr 需要排序的数组
     */
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minSite = i;
            for (int j = i; j<arr.length; j++) {
                minSite = arr[j] < arr[minSite] ? j : minSite;
            }
            swap(arr, i, minSite);
        }
    }

    /**
     * 交换最小值的位置
     *
     * @param arr 数组
     * @param i 当前遍历的位置
     * @param minSite 最小值的位置
     */
    private static void swap(int[] arr, int i, int minSite) {
        int a = arr[i];
        arr[i] = arr[minSite];
        arr[minSite] = a;
    }