排序算法

默认都是从小到大排序，学习视频链接：https://www.bilibili.com/video/BV1iJ411E7xW

1、冒泡排序

排序原理：相邻两个元素比较，如果前者比后者大，则交换两个元素。每执行一次，都会确定一个最大值，其位置就固定了，下一次就不需要再参与排序了。

时间复杂度：O(n^2)

稳定性：稳定

具体实现：

public class Bubble {
    /**
     * 对数组a中的元素进行排序
     */
    public static void sort(Comparable[] a){
        //每冒泡一次，参与冒泡排序的元素个数就少一个
        //需要排序的次数为数组个数减一
        /*for (int i=a.length-1; i>0; i--){
            for (int j=0; j<i; j++){
                if (greater(a[j],a[j+1])){
                    exch(a, j,j+1);
                }
            }
        }*/
        for (int i=0; i<a.length-1; i++){
            for (int j=0; j<a.length-i-1; j++){
                if (greater(a[j],a[j+1])){
                    exch(a, j,j+1);
                }
            }
        }
    }

    /**
     * 比较u元素是否大于v元素
     */
    private static boolean greater(Comparable u, Comparable v){
        return u.compareTo(v) > 0;
    }

    /**
     * 交换数组下标为i和j的元素的位置
     */
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
	/**
     * 测试
     */
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6};
        sort(a);
        System.out.println(Arrays.toString(a));
    }

}

优化：可以加一个标志位，当冒泡一次也没有执行的时候，就说明已经排好了，就不需要再冒泡了。

2、选择排序

排序原理：从数组中找出最小值的下标，然后将最小值交换到前边。每执行一次前边就会有一个最小值位置固定，之后就不再需要参与查找最小值了。

时间复杂度：O(n^2)

稳定性：不稳定

具体实现：

public class Selelction {
    /**
     * 将数组排序
     * @param a 待排序的数组
     */
    public static void sort(Comparable[] a){
        for (int i=0; i<a.length-1; i++){
            //找出最小的值
            int minIndex = i;
            //注意这里不需要减一
            for (int j=i+1; j<a.length; j++){
                //Comparable数组 不能直接用下标比较大小
                if (greater(a[minIndex],a[j])){
                    minIndex = j;
                }
            }
            //交换
            if (minIndex != i){
                exch(a, minIndex, i);
            }
        }
    }

    /**
     * 比较第一个参数是否大于第二个参数
     * @param a
     * @param b
     * @return 第一个参数是否大于第二个参数
     */
    private static boolean greater(Comparable a, Comparable b){
        return a.compareTo(b) > 0;
    }

    /**
     * 交换数组的两个元素
     * @param a 数组
     * @param i 数组下标
     * @param j 数组下标
     */
    private  static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 测试方法
     * @param args
     */
    public static void main(String[] args) {
        Integer[] array = {1,6,7,3,2,5,7,8,4,0,5,3,7};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

3、简单插入排序

排序原理：将数组分成两组，左边一组是已排序的，右边一组是未排序的，然后拿未排序的第一个与左边的从后往前比较，如果比前边的小就交换，直到前边的值比它小或者等于它。

时间复杂度：O(n^2)

稳定性：稳定

具体实现：

public class Insertion {
    /**
     * 对数组a中的元素进行排序
     */
    public static void sort(Comparable[] a){
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j > 0; j--){
                if (greater(a[j-1],a[j])){
                    exch(a, j-1, j);
                }else {
                    break;
                }
            }
        }
    }

    /**
     * 比较u元素是否大于v元素
     */
    private static boolean greater(Comparable u, Comparable v){
        return u.compareTo(v) > 0;
    }

    /**
     * 交换数组下标为i和j的元素的位置
     */
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

优化思路：将要插入的数先保存起来，然后交换的代码就可以改成覆盖，就相当于后移，等找到合适位置再把之前保存的值放进去。

4、希尔排序

排序原理：是插入排序的优化版，插入排序在比较时只能一个一个比较，而希尔排序中加了一个增长量，可以跨元素比较，相对减少了比较交换的次数。

时间复杂度：O(n^1.3)

稳定性：不稳定

具体实现：

public class Shell {
    /**
     * 将数组排序
     * @param a 待排序的数组
     * @return 排好序的数组
     */
    public static void sort(Comparable[] a){
        //1.确定增长量h的值
        int h=1;
        while(h < a.length/2){
            h = h*2+1;
        }
        //2.进行排序
        while(h>=1){
            //找到待排序的第一个值
            for (int i=h; i<a.length; i++){
                for (int j=i; j>=h; j-=h){
                    if (greater(a[j-h],a[j])){
                        exch(a, j, j-h);
                    }else{
                        break;
                    }
                }
            }
            //h减小
            h/=2;
        }
    }

    /**
     * 比较u元素是否大于v元素
     */
    private static boolean greater(Comparable u, Comparable v){
        return u.compareTo(v) > 0;
    }

    /**
     * 交换数组下标为i和j的元素的位置
     */
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    //测试数据
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8, 6, 7};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

5、归并排序

排序原理：使用了递归的思想，先把数组从中间递归分解，接着先排序左边的子数组，然后再排序右边的子数组，最后合并为一个数组。核心方法是merge方法。

时间复杂度：O(nlogn)

稳定性：稳定

具体实现：

public class Merge {
    /**
     * 辅助数组
     */
    private static Comparable[] access;

    /**
     * 对数组a进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        //1.初始化辅助数组
        access = new Comparable[a.length];
        //2.定义两个下标值
        int lo = 0;
        int hi = a.length -1;
        //3.调用分组排序函数
        sort(a, lo, hi);
    }

    /**
     * 对数组a中的lo到hi进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi){
        //保护
        if (hi <= lo){
            return;
        }
        //1.得到mid
        int mid = lo + (hi-lo)/2;
        //2.对左数组分组排序
        sort(a, lo, mid);
        //3.对右数组分组排序
        sort(a, mid+1, hi);
        //4.将两个数组合并
        merge(a, lo, mid, hi);
    }

    /**
     * 将两个数组进行排序合并
     * @param a
     * @param lo
     * @param mid
     * @param hi
     */
    private static void merge(Comparable[] a, int lo, int mid, int hi){
        //1.定义三个指针
        int i=lo;
        int p1=lo;
        int p2=mid+1;
        //2.分别遍历两个子数组，直到有一个数组遍历完毕
        while (p1 <= mid && p2 <= hi){
            if (less(a[p1], a[p2])){
                access[i++] = a[p1++];
            }else{
                access[i++] = a[p2++];
            }
        }
        //3。将剩下的一个数组的剩余值放到辅助数组中
        while(p1 <= mid){
            access[i++] = a[p1++];
        }
        while(p2 <= hi){
            access[i++] = a[p2++];
        }
        //4。将辅助数组中的值覆盖到原数组中
        for (int index=lo; index<=hi; index++){
            a[index] = access[index];
        }
    }

    /**
     * 比较第一个下标的值是不是小于第二个下标的值
     * @param u
     * @param v
     * @return
     */
    private static boolean less(Comparable u, Comparable v){
        return u.compareTo(v) <= 0;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

6、快速排序

排序原理：把数组的第一个值设置为中间值，比中间值小的放到左边，比中间值大的放到右边。然后再对左边的做相同的操作，最后是对右边的做相同的操作。核心方法是partition方法，将小的数移到左边，大的数移到右边，最后返回中间值的下标。

时间复杂度：O(nlogn)

稳定性：不稳定

具体实现：

public class Quick {
    /**
     * 对数组a进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        int lo = 0;
        int hi = a.length-1;
        sort(a, lo, hi);
    }

    /**
     * 对数组a中的lo到hi进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi){
        //保护
        if (hi <= lo){
            return;
        }
        //获取中间值
        int mid = partition(a, lo, hi);
        //对左子数组进行排序
        sort(a, lo, mid-1);
        //对右子数组进行排序
        sort(a, mid+1, hi);
    }


    /**
     * 将比子数组中第一个值小的数放到其左边，大于的放到右边，最后返回中间值的下标
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    private static int partition(Comparable[] a, int lo, int hi){
        //1.定义两个指针
        int p1= lo;
        int p2 = hi+1;
        while (true){
            //2.先移动右指针，找到第一个小于标准值的数
            while(less(a[lo],a[--p2])){
                if (p2 == lo){
                    break;
                }
            }
            //3.移动左指针，找到第一个大于标准值的数
            while(less(a[++p1],a[lo])){
                if (p1 == hi){
                    break;
                }
            }
            if (p1 >= p2){
                //5.退出循环
                break;
            }else {
                //4.交换两个值
                exch(a, p1, p2);
            }
        }
        //6.最后把子数组的第一个值和右指针所指的值交换，最后返回其下标
        exch(a, lo, p2);
        return p2;
    }

    /**
     * 比较第一个下标的值是不是小于第二个下标的值
     * @param u
     * @param v
     * @return
     */
    private static boolean less(Comparable u, Comparable v){
        return u.compareTo(v) < 0;
    }

    /**
     * 交换数组中两个下标的值
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}