package com.jiucaiyuan.net.algrithm.sort;



/**

 * 选择法排序

 *  循环待排序数组，i~N-1位置，每次循环找到最小值放到i位置上，然后i++，再次找最小值

 * 排序结果是升序数组

 * 时间复杂度O(N^2)    空间复杂度O(1)

 *

 * @Author jiucaiyuan  2022/3/25 21:48

 * @mail services@jiucaiyuan.net

 */



public class SelectSort {



    public static void selectionSort(int[] arr) {

        if (arr == null || arr.length < 2) {

            return;

        }

        for (int i = 0; i < arr.length; i++) {

            //每次循环记录最小数值的index

            int minIndex = i;

            //从i~N-1个数中找到最下值的下标

            for (int j = i; j < arr.length; j++) {

                minIndex = arr[j] < arr[minIndex] ? j : minIndex;

            }

            //找到最小的数值，和当前i位置对调

            swap(arr, minIndex, i);

        }

    }



    private static void swap(int[] arr, int i, int j) {

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }



    public static void main(String[] args) {

        int[] arr = {1,2,8,3,5,7,2,7,8,12,4};

        selectionSort(arr);

        print(arr);

    }



    private static void print(int[] arr) {

        if(arr == null ){

            return;

        }

        for(int a : arr){

            System.out.print(a+"\t");

        }

        System.out.println();

    }

}