基于java实现的选择排序

选择排序是一种简单直白的排序算法，它的思想是：每次从无序区中选择出最小（或最大）的元素，然后把它和无序区首部的元素交换，此时有序区长度+1，无序区长度-1。

实现思路：

①在排序开始前，整个数组都是无序的，所以此时有序区的长度为0 ===> 找出整个数组中最小（或最大）的元素，将它与无序区首部的元素，即arr[0]交换；

   此时有序区长度为1，无序区长度为length-1；

②在无序区中查找最小的元素，并与无序区首部元素交换 ===>此时有序区长度为2，无序区长度为length-2

……

如此不断，每次都从余下的无序区中找到相应的元素，并且与无序区首部的元素交换。

可以看出，选择排序的时间复杂度为O(N²)。

代码实现：

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数组大小：");
        int size = sc.nextInt();
        int[] arr = new int[size];
        System.out.println("请输入数组：");
        for(int i = 0; i < size; i++) {
            arr[i] = sc.nextInt();
        }
        selectionSort(arr);
        for(int a : arr) {
            System.out.print(a + " ");
        }
    }
    
    public static void selectionSort(int[] arr) {
        if(arr == null || arr.length <= 1)
            return;
        for(int i = 0; i < arr.length - 1; i++) {
            int minIdx = i, minVal = arr[i];
            for(int j = i + 1; j <arr.length; j++) {
                if(arr[j] < minVal) {
                    minVal = arr[j];
                    minIdx = j;
                }
            }
            if(minIdx != i) {
                int temp = arr[i];
                arr[i] = minVal;
                arr[minIdx] = temp;
            }
        }
    }
}