算法数据与结构——排序算法基础（选择排序法、插入排序法）

DBC 1.6K 0

选择排序法

算法数据与结构——排序算法基础（选择排序法、插入排序法）插图
算法数据与结构——排序算法基础（选择排序法、插入排序法）插图2

温馨提示

排序过程中占用了额外的空间
可否原地完成？——原地排序

小例子

package SelectionSort;

public class SelectionSort {
    private SelectionSort() {
    }

    public static void sort(int[] arr) {
        // 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] < arr[minIndex])
                    minIndex = j;
            }
            swap(arr, i, minIndex);
        }
    }


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

    }

    public static void main(String[] args) {

        int[] arr = {1, 4, 2, 3, 6, 5};
        SelectionSort.sort(arr);
        for (int e : arr)
            System.out.print(e + " ");
        System.out.println();
    }
}
控制台输出
温馨提示

这里要注意，下面图片的提示位置，这里博主就犯了小疏忽，这两个嵌套的for循环一定要好好注意才行！

算法数据与结构——排序算法基础（选择排序法、插入排序法）插图4

修改排序算法小例子为泛型

避免篇幅过长，这里仅给出关键代码

    //对泛型进行约束
    public static <E extends Comparable<E>> void sort(E[] arr) {
        // 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   >就是>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;

    }
        Integer[] arr = {1, 4, 2, 3, 6, 5};
        SelectionSort.sort(arr);
温馨提示

相信认真看文章的看到这里应该也很清晰了，这里最主要需要注意的点有几点。
一、对泛型进行约束，使用到了Comparable，需要好好学习。
二、if (arr[j].compareTo(arr[minIndex])< 0 ) // < 就是<0 >就是>0 这个简单的操作一定要知道。
三、int的数组不能用了，需要改为包装类Integer

使用compareTo接口

在学习之前，我们先重点要知道一个思想，这个也是我首页设计模式的类似思想，这里会有一些体现：
我们的排序算法不关心你是如何实现的，你的具体如何实现，我们通常是由类的设计者来实现！

老规矩，我们一个自定义的student类，里面重写的是compareTo的对比方法，具体思想是我们对比学生的学习成绩来进行排序
package SelectionSort;

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 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.toLowerCase().equals(another.name.toLowerCase());
    }

    @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;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
}
温馨提示

我有注释掉三个if判断，这些代码可以由一行替代，这种写法更加的优雅，可以好好的学习！

我们直接看main方法的具体使用
    public static void main(String[] args) {

        Student[] students = {new Student("白萝卜", 100),
                new Student("大白菜", 99),
                new Student("小马哥", 78)};
        SelectionSort.sort(students);
        for (Student student:students){
            System.out.println(student);
        }
    }

控制台输出

前面我们是从小到大排序，我们如果想改造成从大到小怎么操作呢？

return this.score - another.score;
温馨提示

我们只需要将student类的这个关键代码反过来就可以了，是不是很方便！

上面小例子的排序复杂度分析

    public static void main(String[] args) {

        //0.064107 s
        int[] dataSize = {10000, 100000};
        for(int n: dataSize){
            Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
            SortingHelper.sortTest("SelectionSort", arr);
        }
    }
随机生成数组内容
package SelectionSort;

import java.util.Random;

public class ArrayGenerator {

    private ArrayGenerator(){}

    public static Integer[] generateOrderedArray(int n){

        Integer[] arr = new Integer[n];
        for(int i = 0; i < n; i ++)
            arr[i] = i;
        return arr;
    }

    // 生成一个长度为 n 的随机数组，每个数字的范围是 [0, bound)
    public static Integer[] generateRandomArray(int n, int bound){

        Integer[] arr = new Integer[n];
        Random rnd = new Random();
        for(int i = 0; i < n; i ++)
            arr[i] = rnd.nextInt(bound);
        return arr;
    }
}
校验是否完成排序
public class SortingHelper {

    private SortingHelper(){}

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){

        for(int i = 1; i < arr.length; i ++)
            if(arr[i - 1].compareTo(arr[i]) > 0)
                return false;
        return true;
    }

    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){

        long startTime = System.nanoTime();
        if(sortname.equals("SelectionSort"))
            SelectionSort.sort(arr);
        long endTime = System.nanoTime();

        double time = (endTime - startTime) / 1000000000.0;

        if(!SortingHelper.isSorted(arr))
            throw new RuntimeException(sortname + " failed");
        System.out.println(String.format("%s , n = %d : %f s", sortname, arr.length, time));
    }
}
控制台输出

我们之前是从数组的最前面开始排序，那我们能不能从最后面开始排序呢？

    public static <E extends Comparable<E>> void sort2(E[] arr) {
        // arr[0...i) 是有序的；arr[i...n) 是无序的
        for (int i = arr.length-1; i > 0; i--) {
            // 选择 arr(0。。。i] 中的最小值索引
            int minIndex = i;
            for (int j = i; j >=0; j--) {
                if (arr[j].compareTo(arr[minIndex]) > 0)  // < 就是<0   >就是>0  这个简单的操作一定要知道
                    minIndex = j;
            }
            swap(arr, i, minIndex);
        }
    }
温馨提示

这里最主要的是平常我们都是定义i为0，然后慢慢自增，现在我们反过来，直接定义i为数组中的最大，然后在慢慢的自减！

插入排序法

package InsertionSort;

public class InsertionSort {
    private InsertionSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //将 arr[i] 插入到合适的位置
            for (int j = i; j - 1 >= 0; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    /**
     * 简单的数组元素交换
     *
     * @param arr
     * @param i
     * @param j
     * @param <E>
     */
    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[] date = {1,2,2,85,7,6,5};
        sort(date);
        for (int e:date){
            System.out.println(e);
        }
    }

}
这里代码也可以再升级，会看起来比较简洁，但是逻辑不是很清晰，时间基本一样，看个人喜欢
    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //将 arr[i] 插入到合适的位置
//            for (int j = i; j - 1 >= 0; j--) {
//                if (arr[j].compareTo(arr[j - 1]) < 0) {
//                    swap(arr, j, j - 1);
//                } else {
//                    break;
//                }
//            }
            //升级代码
            for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
                swap(arr, j, j - 1);
            }
        }
    }

插入排序算法的小优化

    public static <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //将 arr[i] 插入到合适的位置
            E t = arr[i];
            int j;
            for (j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j-1];
            }
            arr[j] = t;
        }
    }

插入排序法的重要特性

温馨提示

在插入排序法中的复杂度有如下特点

无序数组——O（n^2）
有序数组——O（n）

但是我们基本不可能会得到有序的，所以一般都是按照无序来算！

选择排序法的复杂度都是O（n^2）

在大部分都是有序的数组，我们使用插入排序法要比选择排序法的速度要快，原因也就是上面说的了！

本文作者为DBC，转载请注明。

发表评论 取消回复
表情 图片 链接 代码

分享