2.选择排序法

1. 先把最小的拿出来
2. 剩下的，再把最小的拿出来
3. 剩下的，再把最小的拿出来
4. 每次选择还没处理的元素里最小的元素

• 新开辟一个数组？ 占用了额外空间。

• 选择排序算法是可以进行原地排序的算法

  原地排序

• arr[i…n)未排序, arr[0…i) 已排序 => 循环不变量

• arr[i…n)中的最小值要放到arr[j]的位置

数据规模扩大10倍，耗时增加了100倍，可以看出是n^2级别的时间复杂度

public class SelectionSort {
    private SelectionSort() {
    }
    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //选择arr[i...n)中最小值的索引
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }
    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        Integer[] arr = {1, 5, 7, 4, 6, 9};
        SelectionSort.sort(arr);
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
        Student[] students = {new Student("Alice", 22), new Student("Bobo", 18), new Student("Jack", 33)};
        SelectionSort.sort(students);
        for (Student student : students) {
            System.out.println(student);
        }
    }
}
public class Student implements Comparable<Student> {
    private String name;
    private int score;
    public Student(String name) {
        this.name = name;
    }
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null) {
            return false;
        }
        if (this.getClass() != o.getClass()) {
            return false;
        }
        Student another = (Student) o;
        return this.name.equals(another.name);
    }
    @Override
    public int compareTo(Student o) {
        return this.score - o.score;
    }
    @Override
    public String toString() {
        return "Student(" +
                "name='" + name + '\'' +
                ", score=" + score +
                ')';
    }
}