排序基础（一）选择排序

最后更新于：2022-08-17 16:11:20

什么是选择排序

给我们一堆混乱的数据，让我们把他按从小到大的顺序排列好。我们第一步是先把其中最下的拿出来，放在第一位，然后再把剩下的数据中最下的拿出来放在第二位，以此类推，每次都选择还未处理的元素总最小的元素，直到完成排序
那么，在一趟选择时，如果当前锁定元素比后面一个元素大，而后面较小的那个元素又出现在一个与当前锁定元素相等的元素后面，那么交换后位置顺序显然改变了。
举个例子：序列5 8 5 2 9， 我们知道第一趟选择第 1 个元素 5 会与 2 进行交换，那么原序列中两个5的相对先后顺序也就被破坏了。
所以选择排序不是一个稳定的排序算法。

实现选择排序

public class SelectSort {

    private SelectSort() {}
    // 使用Comparable来约束泛型必须是可比较的
    public static > void ASC(T[] datas) {
        int size = datas.length;
        for (int i = 0; i < size; i++) {
            Integer minIndex = i;
            // 寻找arr[i,n)中最小的元素
            for (int j = i; j < size; j++) {
                if (datas[j].compareTo(datas[minIndex]) == -1) {
                    minIndex = j;
                }
            }
            // 直接交换最小元素的位置，这样就可以不用创建新的空间来存放元素
            swap(datas, i, minIndex);
        }
    }

    public static  void swap(T[] arr, int i, int j) {
        T t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

}

使用自定义类测试排序

public class Student implements Comparable {

    Integer id;

    String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Student(String name, int id) {
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return name.hashCode() + id;
    }

    @Override
    /**
     * 默认比较的是类对象的地址，所以需要重写成我们认为相同的条件
     */
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (!(obj instanceof Student)) {
            return false;
        }
        Student student = (Student) obj;
        return Objects.equals(this.name, student.getName());
    }

    @Override
    /**
     * 重写自定义类比较方法
     */
    public int compareTo(Student student) {
        if (student.getId() == id) {
            return 0;
        }
        return student.getId() < this.id ? 1 : -1;
    }

    @Override
    public String toString() {
        return "Student(" +
                "id:" + id +
                ", name:'" + name + '\'' +
                ')';
    }
}

测试

    public static void main(String[] args) {
        Student[] students = {new Student("a", 5),
                new Student("b", 2),
                new Student("c", 3),
        };
        SortHelper.sortTest("SelectionSort", students);
        for (Student stu : students) {
            System.out.println(stu);
        }
}

结果

SelectionSort,n = 3 : 0.000026 s
Student(id:2, name:'b')
Student(id:3, name:'c')
Student(id:5, name:'a')

排序结果符合预期结果

时间复杂度分析

测试

    public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n : dataSize) {
            Integer[] datas = ArrayGenerator.generatorRandomArray(n, n);
            SortHelper.sortTest("SelectionSort", datas);
        }
    }

结果

SelectionSort,n = 10000 : 0.107992 s
SelectionSort,n = 100000 : 10.428911 s

从结果看，数据增加了10倍，时间性能增加了100倍，由此可以得出选择排序的时间复杂度为O(n)²级别的