【Java】数据结构-选择排序法

孤樱懶契

选择排序法

• 原理就是不断将剩下元素中最小的数拿出来

  • 

选择排序算法执行截图

（完整代码）选择排序算法基础代码

public class SelectionSort {

    private SelectionSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){  //泛型 扩展 compareable 接口

        // arr[0...i)是有序的； arr[i...n)是无序的
        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)  // 返回的是整型，小于0代表前者小于后者
                    minIndex=j; //存的最小值所对应的索引
            }

            swap(arr, i, minIndex);
        }
    }

    private static <E> void swap(E[] arr, int i , int j){

        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args){

        Integer[] arr = {1, 4, 2, 3, 6, 5};
        SelectionSort.sort(arr);
        for(int e: arr)
            System.out.print(e + " ");
        System.out.println();
    }
}

选择排序算法“优化”类排序执行截图

（完整代码）选择排序选择排序算法“优化”类成员数值排序

SelectionSort.java

public class SelectionSort {

    private SelectionSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){  //泛型 扩展 compareable 接口

        // arr[0...i)是有序的； arr[i...n)是无序的
        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)  // 返回的是整型，小于0代表前者小于后者
                    minIndex=j; //存的最小值所对应的索引
            }

            swap(arr, i, minIndex);
        }
    }

    private static <E> void swap(E[] arr, int i , int j){

        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args){

        Integer[] arr = {1, 4, 2, 3, 6, 5};
        SelectionSort.sort(arr);
        for(int e: arr)
            System.out.print(e + " ");
        System.out.println();

        Student[] students = {new Student("Alice", 98),
                            new Student("Bob", 100),
                            new Student("Charles", 66)};
        SelectionSort.sort(students);
        for(Student student: students)
            System.out.print(student + " ");
        System.out.println();
    }
}

(Override)覆盖方法Student.java

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 0;
//          return 1;
        return this.score - another.score; //优雅写法 从小到大按分数排序
//          return another.score - this.score;  //从大到小按分数进行排序
    }

    @Override
    public boolean equals(Object student){
        if(this == student)
            return true;
        if(student == null)
            return false;

        if(this.getClass() != student.getClass())
            return false;

        Student another = (Student)student;
        return this.name.equals(another.name);
    }

    @Override
    public String toString(){
        return String.format("Student(name: %s, score: %d)", name, score);
    }
}

ytlk0535

感谢楼主分享，备用以后学了

niusan521

if(arr[j].compareTo(arr[minIndex]) < 0)    这是在作比较吗？
  compareTo(arr[minindex])  这是啥意思？

孤樱懶契

niusan521 发表于 2021-7-2 13:09
if(arr[j].compareTo(arr[minIndex]) < 0)    这是在作比较吗？
  compareTo(arr[minindex])  这是啥意思 ...

因为设定是泛型
所以比较大小只能使用compareTo这个来进行大小比较
j 和 minIndex   如果j > min*  则返回>0
j 和 minIndex   如果j = min*  则返回=0
j 和 minIndex   如果j < min*  则返回<0