选择排序

1. 原理

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

2. 特性

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

3. 图示

4. 时间 & 空间复杂度

平均	最好	最坏	空间	稳定性
O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定

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+" ");
       
        }
}