基于java实现的选择排序

旧城等待， 2022-12-11 03:12 6阅读 0赞

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

实现思路：

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

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

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

……

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

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

代码实现：

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;
                }
            }
        }
    }