感谢小码哥的 恋上数据结构，记录课程笔记。

我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

建议先看一下这篇博客： 复杂度知识以及LeetCode刷题指南。

何为排序？

• 排序前：$3, 1, 6, 9, 2, 5, 8, 4, 7$
• 升序排序：$1, 2, 3, 4, 5, 6, 7, 8, 9$
• 降序排序： $9, 8, 7, 6, 5, 4, 3, 2, 1$

何为稳定性？

如果相等的 2 个元素，在排序前后的相对位置保持不变那么这是稳定的排序算法。

• 排序前：$5, 1, 3_a, 7, 3_b$
• 稳定的排序： $1, 3_a, 3_b, 4, 5, 7$
• 不稳定的排序： $1, 3_b, 3_a, 4, 5, 7$

对自定义对象进行排序时，稳定性会影响最终的排序效果。

何为原地算法？

• 不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
• 空间复杂度为$O(1)$的都可以认为是原地算法
• 非原地算法，称为 Not-in-place 或者 Out-of-place

时间复杂度的知识

请看这个：复杂度知识以及LeetCode刷题指南

写排序算法前的准备

项目结构

创建一个项目，大体结构是这样的：

以下包名省略 com.mj

• sort：各种排序类

  • cmp：比较类排序
  • sort.java 排序抽象类

• tools：排序中用到的工具

  • Asserts.java 单元测试
  • Inegers.java 生成测试数据
  • Time.java 计算时间
• Main 主函数，写排序测试
• Student.java 利用自定义类测试稳定性(sort.java中使用)

Sort.java

写一个抽象类 Sort.java

• 实现自定义对象的比较(cmp)，交换(swap)方法
• 同时可以用来计算比较次数(cmpCount)，交换次数(swapCount)，花费时间(time)
• 排序是否稳定()

@SuppressWarnings("unchecked")
public abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> {
    protected T[] array;
    private int cmpCount;
    private int swapCount;
    private long time;
    private DecimalFormat fmt = new DecimalFormat("#.00");
    
    public void sort(T[] array) {
        if (array == null || array.length < 2) return;
        
        this.array = array;
        
        long begin = System.currentTimeMillis();
        sort();
        time = System.currentTimeMillis() - begin;
    }
    
    @Override
    public int compareTo(Sort<T> o) {
        int result = (int)(time - o.time);
        if (result != 0) return result;
        
        result = cmpCount - o.cmpCount;
        if (result != 0) return result;
        
        return swapCount - o.swapCount;
    }
    
    protected abstract void sort();
    
    /*
     * 返回值等于0，代表 array[i1] == array[i2]
     * 返回值小于0，代表 array[i1] < array[i2]
     * 返回值大于0，代表 array[i1] > array[i2]
     */
    protected int cmp(int i1, int i2) {
        cmpCount++;
        return array[i1].compareTo(array[i2]);
    }
    
    protected int cmp(T v1, T v2) {
        cmpCount++;
        return v1.compareTo(v2);
    }
    
    protected void swap(int i1, int i2) {
        swapCount++;
        T tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }
    
    @Override
    public String toString() { 
        String timeStr = "耗时：" + (time / 1000.0) + "s(" + time + "ms)";
        String compareCountStr = "比较：" + numberString(cmpCount);
        String swapCountStr = "交换：" + numberString(swapCount);
        String stableStr = "稳定性：" + isStable();
        return "【" + getClass().getSimpleName() + "】\n" 
                + stableStr + " \t"
                + timeStr + " \t"
                + compareCountStr + "\t "
                + swapCountStr + "\n"
                + "------------------------------------------------------------------";
    }
    
    private String numberString(int number) {
        if (number < 10000) return "" + number;
        
        if (number < 100000000) return fmt.format(number / 10000.0) + "万";
        return fmt.format(number / 100000000.0) + "亿";
    }
    
    private boolean isStable() {
        if (this instanceof RadixSort) return true;
        if (this instanceof CountingSort) return true;
        if (this instanceof ShellSort) return false;
        if (this instanceof SelectionSort) return false;
        
        Student[] students = new Student[20];
        for (int i = 0; i < students.length; i++) {
            students[i] = new Student(i * 10, 10);
        }
        sort((T[]) students);
        for (int i = 1; i < students.length; i++) {
            int score = students[i].score;
            int prevScore = students[i - 1].score;
            if (score != prevScore + 10) return false;
        }
        return true;
    }
}

Asserts.java

public class Asserts {
    public static void test(boolean value) {
        try {
            if (!value) throw new Exception("测试未通过");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Integers.java

public class Integers {
    public static Integer[] random(int count, int min, int max) {
        if (count <= 0 || min > max) return null;
        Integer[] array = new Integer[count];
        int delta = max - min + 1;
        for (int i = 0; i < count; i++) {
            array[i] = min + (int)(Math.random() * delta);
        }
        return array;
    }
    
    public static Integer[] combine(Integer[] array1, Integer[] array2) {
        if (array1 == null || array2 == null) return null;
        Integer[] array = new Integer[array1.length + array2.length];
        for (int i = 0; i < array1.length; i++) {
            array[i] = array1[i];
        }
        for (int i = 0; i < array2.length; i++) {
            array[i + array1.length] = array2[i];
        }
        return array;
        
    }
    
    public static Integer[] same(int count, int unsameCount) {
        if (count <= 0 || unsameCount > count) return null;
        Integer[] array = new Integer[count];
        for (int i = 0; i < unsameCount; i++) {
            array[i] = unsameCount - i;
        }
        for (int i = unsameCount; i < count; i++) {
            array[i] = unsameCount + 1;
        }
        return array;
    }
    
    public static Integer[] headTailAscOrder(int min, int max, int disorderCount) {
        Integer[] array = ascOrder(min, max);
        if (disorderCount > array.length) return array;
        
        int begin = (array.length - disorderCount) >> 1;
        reverse(array, begin, begin + disorderCount);
        return array;
    }
    
    public static Integer[] centerAscOrder(int min, int max, int disorderCount) {
        Integer[] array = ascOrder(min, max);
        if (disorderCount > array.length) return array;
        int left = disorderCount >> 1;
        reverse(array, 0, left);
        
        int right = disorderCount - left;
        reverse(array, array.length - right, array.length);
        return array;
    }
    
    public static Integer[] headAscOrder(int min, int max, int disorderCount) {
        Integer[] array = ascOrder(min, max);
        if (disorderCount > array.length) return array;
        reverse(array, array.length - disorderCount, array.length);
        return array;
    }
    
    public static Integer[] tailAscOrder(int min, int max, int disorderCount) {
        Integer[] array = ascOrder(min, max);
        if (disorderCount > array.length) return array;
        reverse(array, 0, disorderCount);
        return array;
    }
    
    public static Integer[] ascOrder(int min, int max) {
        if (min > max) return null;
        Integer[] array = new Integer[max - min + 1];
        for (int i = 0; i < array.length; i++) {
            array[i] = min++;
        }
        return array;
    }
    
    public static Integer[] descOrder(int min, int max) {
        if (min > max) return null;
        Integer[] array = new Integer[max - min + 1];
        for (int i = 0; i < array.length; i++) {
            array[i] = max--;
        }
        return array;
    }
    
    /**
     * 反转一个数组，索引范围是[begin, end)
     */
    private static void reverse(Integer[] array, int begin, int end) {
        int count = (end - begin) >> 1;
        int sum = begin + end - 1;
        for (int i = begin; i < begin + count; i++) {
            int j = sum - i;
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }
    
    public static Integer[] copy(Integer[] array) {
        return Arrays.copyOf(array, array.length);
    }
    
    public static boolean isAscOrder(Integer[] array) {
        if (array == null || array.length == 0) return false;
        for (int i = 1; i < array.length; i++) {
            if (array[i - 1] > array[i]) return false;
        }
        return true;
    }
    
    public static void println(Integer[] array) {
        if (array == null) return;
        StringBuilder string = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            if (i != 0) string.append("_");
            string.append(array[i]);
        }
        System.out.println(string);
    }
}

Times.java

public class Times {
    private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
    
    public interface Task {
        void execute();
    }
    
    public static void test(String title, Task task) {
        if (task == null) return;
        title = (title == null) ? "" : ("【" + title + "】");
        System.out.println(title);
        System.out.println("开始：" + fmt.format(new Date()));
        long begin = System.currentTimeMillis();
        task.execute();
        long end = System.currentTimeMillis();
        System.out.println("结束：" + fmt.format(new Date()));
        double delta = (end - begin) / 1000.0;
        System.out.println("耗时：" + delta + "秒");
        System.out.println("-------------------------------------");
    }
}

Student.java

public class Student implements Comparable<Student> {
    public int score;
    public int age;
    
    public Student(int score, int age) {
        this.score = score;
        this.age = age;
    }
    
    @Override
    public int compareTo(Student o) {
        return age - o.age;
    }
}

排序算法测试

把上面的工具代码配置好，我们就可以来写排序算法并且测试啦。

首先写一个简单的冒泡排序。

由于冒泡排序属于比较排序，我们将它放到cmp包下。

BubbleSort1.java

/**
 * 冒泡排序-无优化
 */
public class BubbleSort1<T extends Comparable<T>> extends Sort<T>{
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                }
            }
        }
    }
}

此时目录结构应该与我一开始发的完全一样了，可以来测试排序代码了。

Main.java

@SuppressWarnings({ "rawtypes", "unchecked" })
public class Main {
    // 在 main 函数里写测试代码
    public static void main(String[] args) {
        // 产生 20000 个数据,每个数据的范围是 1~10000
        Integer[] array = Integers.random(20000, 1, 10000);    
        // 在这里面写要测试的代码
        testSorts(array, 
                new BubbleSort1()        // 冒泡排序
                );
    }
    
    // 下面这个复制就可以
    static void testSorts(Integer[] array, Sort... sorts) {
        for (Sort sort : sorts) {
            Integer[] newArray = Integers.copy(array);
            sort.sort(newArray);
            Asserts.test(Integers.isAscOrder(newArray));
        }
        Arrays.sort(sorts);
        for (Sort sort : sorts) {
            System.out.println(sort);
        }
    }

}

目前只有一个冒泡排序，运行结果如下：

以后我们写了多个排序算法做测试，效果是这样的：

@SuppressWarnings({ "rawtypes", "unchecked" })
public class Main {
    public static void main(String[] args) {
        // 产生 20000 个数据,每个数据的范围是 1~10000
        Integer[] array = Integers.random(20000, 1, 10000);    

        testSorts(array, 
                new BubbleSort1(),        // 冒泡排序
//                new BubbleSort2(),        // 冒泡排序-优化1
//                new BubbleSort3(),        // 冒泡排序-优化2
                new SelectionSort(),     // 选择排序
                new HeapSort()          // 堆排序
//                new InsertionSort1(),   // 插入排序
//                new InsertionSort2(),     // 插入排序-挪动优化
                new InsertionSort3(),    // 插入排序-二分查找优化
                new MergeSort(),        // 归并排序
                new QuickSort(),        // 快速排序
                new ShellSort(),        // 希尔排序
                new CountingSort(),        // 计数排序
                new RadixSort()            // 基数排序
                );
    }
    
    static void testSorts(Integer[] array, Sort... sorts) {
        for (Sort sort : sorts) {
            Integer[] newArray = Integers.copy(array);
            sort.sort(newArray);
            Asserts.test(Integers.isAscOrder(newArray));
        }
        Arrays.sort(sorts);
        for (Sort sort : sorts) {
            System.out.println(sort);
        }
    }

}