简单排序算法

Comparable 接口

Java 提供了一个接口 Comparable 就是用来定义排序规则的

public class Student implements Comparable<Student>{
    private String name;
    private Integer age;

    public Student(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

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

    @Override
    public int compareTo(Student o) {
        return this.age - o.age;
    }
}

之后实现的排序方法都是需要实现这个 Comparable 接口

public class Temp {
    public static void main(String[] args) {
        Student s1 = new Student("Julie",16);
        Student s2 = new Student("Jake",18);

        Comparable max = getMax(s1, s2);
        System.out.println(max);
    }

    private static Comparable getMax(Comparable c1, Comparable c2) {
        int result = c1.compareTo(c2);
        if (result >=0) {
            return c1;
        } else {
            return c2;
        }
    }
}

例如：

类名	Bubble
构造方法	Bubble()：创建 Bubble 对象
成员方法	1. public static void sort(Comparable[] a): 对数组内的元素进行排序 2. private static void greater(Comparable v, Comparable w): 判断 v 是否比 w 大 3. private static void exch(Comparable[] a, int i, int j): 交换 a 数组中，索引 i和索引 j处的值

所有常用排序时间复杂度

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	稳定
直接插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
希尔排序	O(nlogn)~O(n^2)	O(n^1.3)	O(n^2)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn)~O(n)	不稳定

对应的图

排序的稳定性

同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定性的；否则就没有。

举例：数组中有若干个元素，其中 A元素和 B元素相等，并且 A元素在 B元素前面，如果使用某种排序算法后，能保证 A元素依然在 B元素的前面，那么这个算法是稳定的。

稳定性的意义：如果一组数据只需一次排序，则稳定性没有意义，如果一组数据需要使用多次排序，稳定性则有意义。

例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序则是按照销量由高到低排序，如果第二次排序是稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展示，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，也可以减少系统开销。

稳定排序：             冒泡排序（相等时不交换才能保持稳定）、插入排序、归并排序、基数排序（一切桶排序思想下的排序） 不稳定的排序：      选择排序、快速排序、希尔排序、堆排序

简单排序

冒泡排序

冒泡排序就是比较两个相邻的元素，将值大的元素交换到右边

public class Bubble {
    public static <T extends Comparable<T>> void sort(T[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (greater(a[j], a[j + 1])) {
                    exchange(a, j, j + 1);
                }
            }
        }
    }

    private static <T extends Comparable<T>> boolean greater(T v, T w) {
        return v.compareTo(w) > 0;
    }

    private static <T extends Comparable<T>> void exchange(T[] a, int i, int j) {
        T temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

编写测试类（注意这里应该使用包装类）

public class Temp {
    public static void main(String[] args) {
        Integer[] arr1 = {3,5,1,7,8,2};
        Bubble.sort(arr1);
        System.out.println(Arrays.toString(arr1));
    }
}

对冒泡排序的时间复杂度进行分析：

元素比较的次数为：

(N -1) +(N -2) +(N -3) + ... +2 +1
就是一个等差数列求和公式
= ((N -1) +1) *(N -1)/2
= N^2/2 -N/2

最坏情况（逆序）元素交换次数为：

(N -1) +(N -2) +(N -3) + ... +2 +1
= ((N -1) +1) *(N -1)/2
= N^2/2 -N/2

总执行次数为

(N^2/2 -N/2) + (N^2/2 -N/2)
= N^2-N

按照大 O推导法则，最终冒泡排序的时间复杂度为 $O(N^2)$

补充知识1：等差数列求和公式为: $S_n = \frac {1} {2} n(a_1 + a_n)$ 补充知识2：点进包装类里可以看到它们都实现了这个 Comparable 接口

public final class Integer extends Number
        implements Comparable<Integer>, Constable, ConstantDesc {

冒泡排序算法的优化

可以在冒泡排序加个 flag 如果一次循环中一次修改都没有，则表示这个是已经排序好的

public class Bubble {
    public static <T extends Comparable<T>> void sort(T[] a) {
        boolean flag = false;

        for (int i = a.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (greater(a[j], a[j + 1])) {
                    flag = true;

                    exchange(a, j, j + 1);
                }
            }

            if (!flag) {
                // 在一趟排序中，一次交换都没有发生过说就是按照从小到大排序的
                break;
            }  else {
                // 要进行重置，因为如果上面的改成了 true 没有重置，那下一趟就算全部没有交换它还是 true，就失去了 flag 的意义了
                flag = false;
            }
        }
    }

    // ...
}

选择排序

每一次遍历过程中，都 假定第一个索引处的元素是最小值，和其它索引处的值依次进行比较，如果当前索引处的值大于其它某个索引处的值就交换索引

public class Selection {
    public static <T extends Comparable<T>> void sort(T[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            // 假定本次最小值的索引是 i
            int minIndex = i;
            for (int j = i + 1; j < a.length; j++) {
                if (greater(a[minIndex], a[j])) {
                    // 交换最小值所在索引
                    minIndex = j;
                }
            }
            // 交换 i 索引处的值和 minIndex 所在的值
            exchange(a, i, minIndex);
        }
    }

    private static <T extends Comparable<T>> boolean greater(T v, T w) {
        return v.compareTo(w) > 0;
    }

    private static <T extends Comparable<T>> void exchange(T[] a, int i, int j) {
        T temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

编写测试类

public class Temp {
    public static void main(String[] args) {
        Integer[] arr1 = {3,5,1,7,8,2};
        Selection.sort(arr1);
        System.out.println(Arrays.toString(arr1));
    }
}

选择排序的时间复杂度和冒泡法是一样的，都是 $O(N^2)$

插入排序

把所有的元素分为两组，已经排序的和未排序的；找到未排序的组中的第一个元素，向已经排序的组中进行插入

倒序遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

public class Insertion {

    public static <T extends Comparable<T>> void sort(T[] arr) {
        // 检查数据合法性
        if (arr == null || arr.length <= 0) {
            return;
        }

        // 0~0 有序的
        // 0~i 想有序
        // 这里从 1 开始，因为 0~0 是有序的
        for (int i = 1; i < arr.length; i++) { // 0~i 做到有序
            // 这个 j >= 0 主要是避免下标越界
            for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    private static swap(T[] arr, int i,int j) {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

测试类同上，复杂度也是 $O(N^2)$

插入排序的改良

直接插入排序每次往前插入时，是按顺序依次往前查找，数据量较大时，必然比较耗时，效率低。改进思路： 在往前找合适的插入位置时 采用二分查找的方式，即折半插入。

二分插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至 $O(NlogN)$ ,排序是稳定的，但排序的比较次数与初始序列无关，相比直接插入排序，在速度上有一定提升。逻辑步骤：

① 从第一个元素开始，该元素可以认为已经被排序 ② 取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置 ③ 将新元素插入到该位置后 ④ 重复上述两步

// 注意，这里就不用上面的 exchange 方法了
public class Insertion {
    public static <T extends Comparable<T>> void sort(T[] a) {

        
        for (int i = 1; i < a.length; i++) {
            
            T key = a[i];
            int middle;
            int left = 0;
            int right = i - 1;

            // 这里取得要交换的位置（left），它只是省略了多次 greater(a[j - 1], a[j]) 的过程
            while (left <= right) {
                middle = (left + right) / 2;
                if (greater(a[middle], key))
                    right = middle - 1;
                else
                    left = middle + 1;
            }

            // 要把在这个要交换位置后面的数往后移动一位
            for (int j = i - 1; j >= left; j--) {
                a[j + 1] = a[j];
            }
            // 最后把取得的数添加到对应的位置上（left）
            a[left] = key;
        }
    }

    private static <T extends Comparable<T>> boolean greater(T v, T w) {
        return v.compareTo(w) > 0;
    }
}