一、 基础排序算法

• 排序算法：让数据有序
• 排序算法钟蕴含着重要的算法设计思想
• 两个基础排序算法：选择排序算法、插入排序算法

二、 选择排序法

思路：先把最小的拿出来，再把剩下的里面最小的拿出来，如此反复。

很明显，在排序的过程中使用了额外的空间，那么是否可以原地完成排序？
答：可以原地排序

解法：

arr[i……n) 未排序             arr[0……i)已排序 即循环不变量
arr[i……n) 中的最小值要放到arr[i]的位置

1. 实现选择排序（原地排序 ）

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();
    }

}

2. 使用带约束的泛型

public class SelectionSort {

    private SelectionSort(){}

    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){
                    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();
    }

}

3. 使用 Comparable 接口

public class SelectionSort {

    private SelectionSort(){}

    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){
                    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("Tom",100),
                             new Student("Charles", 66)};
        SelectionSort.sort(students);
        for (Student student:students) { 
            System.out.print(student + " ");
        }
        System.out.println();
    }

}

添加自定义类 Student：

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;
//        }else{
//            return 1;
//        }
//        直接化简成一行(从小到大)，反之则是从大到小
        return this.score - another.score;
    }

    //euqals(Student studnet)是不对的，因为equals是Object父类的方法，我们要覆盖它就要传父类
    @Override
    public boolean equals(Object student){
        // 强制转换可能出异常，我们判断一下
        //当前的对象是否是student类的对象，地址是否一样，也就是是否是同一对象
        if (this == student){
            return true;}
        //传来的student是不是空对象
        if (student == null){
            return false;}
        //判断强制转换是否成功
        if (this.getClass() != student.getClass()){
            return false;
        }
        //强制类型转换，这样就可以进行字符串的比较a
        Student another = (Student)student;
        //转换成小写进行比较
        return this.name.toLowerCase().equals(another.name.toLowerCase());
    }

    @Override
    public String toString (){

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

1 2 3 4 5 6
Student{name: Charles, score: 66} Student{name: Alice, score: 98} Student{name: Tom, score: 100}

4. 选择排序算法的时间复杂度

这里它的时间复杂度是：$O_{(n^2)}$

使用代码简单观察一下：

public class SelectionSort {

    private SelectionSort(){}

    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){
                    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){

       int n =10000;
       Integer[] arr = ArrayGenerator.generateRandomArray(n,n);

       long startTime = System.nanoTime();
       SelectionSort.sort(arr);
       long endTime = System.nanoTime();

       double time = (endTime - startTime) / 1000000000.0;

        System.out.println(time +  " s");
    }

}

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++) {
            //bound 是取值上限（范围前闭后开）
            arr[i] = rnd.nextInt(bound);
        }
        return arr;
    }
}

0.0726749 s

但是现在我们并不确定这一万个数据是否真的排好顺序，所以我们验证一下：相邻两个数据进行比较大小，同时我们封装一下，便于代码复用

public class SelectionSort {

    private SelectionSort(){}

    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){
                    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){

       int[] dataSize = {10000,100000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);

            SortingHelper.sortTest("SelectionSort",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));
    }
}

SelectionSort , n = 10000 : 0.087428 s
SelectionSort , n = 100000 : 8.824518 s

从这里可以看出，数据量差了10倍，所用时间相差近100倍，所以时间复杂度是$O_{(n^2)}$

三、 插入排序法

代码逻辑：

代码实现：

public class InsertionSort {

    private InsertionSort(){}


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

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

    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 void main(String[] args){

        int[] dataSize = {10000,100000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);

            SortingHelper.sortTest("InsertionSort",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);
        }else if (sortname.equals("InsertionSort")){
            InsertionSort.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));
    }
}

InsertionSort , n = 10000 : 0.107390 s
InsertionSort , n = 100000 : 14.425118 s

1. 小优化

import java.util.Arrays;

public class InsertionSort {

    private InsertionSort(){}


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

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

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


    public static void main(String[] args){

        int[] dataSize = {10000,100000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            Integer[] arr2 = Arrays.copyOf(arr, arr.length);

            SortingHelper.sortTest("InsertionSort", arr);
            SortingHelper.sortTest("InsertionSort2", arr2);
        }
    }
}

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);
        }else if (sortname.equals("InsertionSort")){
            InsertionSort.sort(arr);
        }else if (sortname.equals("InsertionSort2")){
            InsertionSort.sort2(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));
    }
}

InsertionSort , n = 10000 : 0.097736 s
InsertionSort2 , n = 10000 : 0.102029 s
InsertionSort , n = 100000 : 14.636478 s
InsertionSort2 , n = 100000 : 10.645270 s

2. 插入排序法的特性

时间复杂度也是$O_{(n^2)}$，但是对于已经有序的数组，插入排序法的时间复杂度是$O_{(n)}$。