选择排序法没有占用多余空间，属于原地排序，先找出最小的，找到了就交换位置。

public class SelectionSort {

    private SelectionSort() {}

    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    /**
     * 把arr数组中索引位置为i和minIndex的元素交换位置
     */
    private static void swap(int[] arr, int i, int minIndex) {
        int t = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = t;
    }
}

测试

@Test
public void SelectionSortTest() {
    int[] dataArray = {1, 7, 5, 9, 3, 11, 5, 6};
    SelectionSort.sort(dataArray);
    for (int data : dataArray) {
        System.out.print(data + " ");
    }
}

选择排序-泛型优化

想一下我们引入泛型后会出现什么问题？数字可以通过大小直接比较，那么对象呢？对象我们可以使用compareTo进行比较，这就对对象进行了限制，只有实现了Comparable接口的对象才能进行比较，因此代码实现如下

public class SelectionSort {

    private SelectionSort() {}

    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            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 minIndex) {
        E t = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = t;
    }
}

自定义类使用选择排序方法

上文提到过，只有实现了Comparable接口的对象才能进行比较，因此对于我们自定义对象该如何进行比较呢？我们也来实现一下Comparable接口，例如学生根据成绩进行排序。

public class Student implements Comparable<Student> {

    private String name;
    private int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
    
    @Override
    public int compareTo(Student another) {
        if (this.score < another.score) {
            return -1;
        } else if (this.score > another.score) {
            return 1;
        }
        return 0;
    }
    
    @Override
    public String toString() {
        return String.format("Student{name=%s, score=$s}", name, score);
    }
}

测试

@Test
public void SelectionSortTest() {
    Student[] studentList = {new Student("张三",99), new Student("李四",5), new Student("王五",31)};
    SelectionSort.sort(studentList);
    for (Student student : studentList) {
        System.out.println(student);
    }
}