import java.util.Arrays;

/**
 * 选择排序算法
 * 中心思路：将待排序数组，按照有序和无序划分成两个部分
 *         在对比过程中，将无序部分最小的与无序部分第一个元素进行交换，依次重复对比
 *         时间复杂度为O(n²)
 */
public class ChooseSort {
    public static void chooseSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[minIndex]>array[j]){
                    // 寻找到数组中无序部分最小的下标
                    minIndex = j;
                }
            }
            // 获取最小的元素下表，并将数据进行交换
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] array = {1,3,2,6,4,5,8,7};
        chooseSort(array);
        System.out.println(Arrays.toString(array));
    }
}