选择排序

1. 原理

• 首先找到数组中最小的那个元素，将它和数组中的第一个元素交换位置。 接着在剩下的元素中找到最小的元素， 将它和数组的第二个元素交换位置。如此反复，直到将整个数组排序。

2. 特性

• 选择排序的运行时间和元素的初始顺序无关。
• 选择排序是不稳定的。(不稳定是指可能会交换相等元素的位置)

3. 图示

4. 时间&空间复杂度

5. 代码实现

public class SelectSort {

    public static void sort(int[] a) {

        for (int i = 0; i < a.length; i++) {
            //首先把min指向第i个元素
            int min = i;
            //每次循环从未排序数字中找出最小数的索引，并赋值给min
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            //交换a[i]和a[min]
            int t = a[i];
            a[i] = a[min];
            a[min] = t;
        }
    }

6. 测试用例

 public static void main(String[] args) {

        //随机输入数字
        Random random = new Random(47);
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(10);
        }
        
        System.out.print("排序前： ");
        for (int x : a) {
            System.out.print(x+" ");
        }
        //选择排序
        SelectSort.sort(a);
        
        System.out.println();
        System.out.print("排序后： ");
        for (int x : a) {
            System.out.print(x+" ");
       
        }
}