开启掘金成长之旅！这是我参加「掘金日新计划 12 月更文挑战」的第30天，点击检查活动详情

一、简略排序

在咱们的程序中，排序对错常常见的一种需求，供给一些数据元素，把这些数据元素按照必定的规矩进行排序。比方查询一些订单，按照订单的日期进行排序；再比方查询一些产品，按照产品的价格进行排序等等。所以，接下来咱们要学习一些常见的排序算法。

在java的开发工具包jdk中，现已给咱们供给了许多数据结构与算法的完结，比方List，Set，Map，Math等等，都是以API的办法供给，这种办法的好处在于一次编写，多处运用。咱们学习jdk的办法，也把算法封装到某个类中，那假如是这样，在咱们写java代码之前，就需求先进行API的规划，规划好之后，再对这些API进行完结。

就比方咱们先规划一套API如下：

然后再运用java代码去完结它。

1、Comparable接口介绍

因为咱们这儿要讲排序，所以肯定会在元素之间进行比较，而Java供给了一个接口Comparable便是用来界说排序规矩的，在这儿咱们以事例的方式对Comparable接口做一个简略的回顾。

需求：

界说一个学生类Student，具有年龄age和名字username两个属性，并经过Comparable接口供给比较规矩；

界说测验类Test，在测验类Test中界说测验办法Comparable getMax(Comparable c1,Comparable c2)完结测验

//学生类
public class Student implements Comparable<Student>{
    private String username;
    private int age;
    public String getUsername() {
        return username;
    }
    public void setUsername(String username) {
        this.username = username;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Student{" +
            "username='" + username + '\'' +
            ", age=" + age +
            '}';
    }
    //界说比较规矩
    @Override
    public int compareTo(Student o) {
        return this.getAge()-o.getAge();
    }
}
//测验类
public class Test {
    public static void main(String[] args) {
        Student stu1 = new Student();
        stu1.setUsername("zhangsan");
        stu1.setAge(17);
        Student stu2 = new Student();
        stu2.setUsername("lisi");
        stu2.setAge(19);
        Comparable max = getMax(stu1, stu2);
        System.out.println(max);
    }
    //测验办法，获取两个元素中的较大值
    public static Comparable getMax(Comparable c1,Comparable c2){
        int cmp = c1.compareTo(c2);
        if (cmp>=0){
            return c1;
        }else{
            return c2;
        }
    }
}

2、冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简略的排序算法。

需求：

排序前：{4,5,6,3,2,1}

排序后：{1,2,3,4,5,6}

排序原理：

比较相邻的元素。假如前一个元素比后一个元素大，就交流这两个元素的方位。
对每一对相邻元素做相同的作业，从开端第一对元素到结尾的最终一对元素。最终最终方位的元素便是最大值。

冒泡排序API规划：

冒泡排序的代码完结：

//排序代码
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);
                }
            }
        }
    }
//比较v元素是否大于w元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
//数组元素i和j交流方位
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
//测验代码
public class Test {
    public static void main(String[] args) {
        Integer[] a = {4, 5, 6, 3, 2, 1};
        Bubble.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

冒泡排序的时刻杂乱度为 ==O(N^2)==

3、挑选排序

需求：

排序前：{4,6,8,7,9,2,10,1}

排序后：{1,2,4,5,7,8,9,10}

排序原理：

每一次遍历的进程中，都假定第一个索引处的元素是最小值，和其他索引处的值顺次进行比较，假如当时索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最终能够找到最小值地点的索引
交流第一个索引处和最小值地点的索引处的值

挑选排序API规划：

挑选排序的代码完结：

public class Selection {
    /*
对数组a中的元素进行排序
*/
    public static void sort(Comparable[] a){
        for (int i=0;i<=a.length-2;i++){
            //假定本次遍历，最小值地点的索引是i
            int minIndex=i;
            for (int j=i+1;j<a.length;j++){
                if (greater(a[minIndex],a[j])){
                    //跟换最小值地点的索引
                    minIndex=j;
                }
            }
            //交流i索引处和minIndex索引处的值
            exch(a,i,minIndex);
        }
    }
    /*
比较v元素是否大于w元素
*/
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    /*
数组元素i和j交流方位
*/
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
//测验代码
public class Test {
    public static void main(String[] args) {
        Integer[] a = {4,6,8,7,9,2,10,1};
        Selection.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

时刻杂乱度为 ==O(N^2)==

4、刺进排序

需求：

排序前：{4,3,2,10,12,1,5,6}

排序后：{1,2,3,4,5,6,10,12}

排序原理：

把一切的元素分为两组，现已排序的和未排序的；
找到未排序的组中的第一个元素，向现已排序的组中进行刺进；
倒叙遍历现已排序的元素，顺次和待刺进的元素进行比较，直到找到一个元素小于等于待刺进元素，那么就把待刺进元素放到这个方位，其他的元素向后移动一位；

刺进排序代码完结：

public class Insertion {
    /*
对数组a中的元素进行排序
*/
    public static void sort(Comparable[] a){
        for (int i=1;i<a.length;i++){
            //当时元素为a[i],顺次和i前面的元素比较，找到一个小于等于a[i]的元素
            for (int j=i;j>0;j--){
                if (greater(a[j-1],a[j])){
                    //交流元素
                    exch(a,j-1,j);
                }else {
                    //找到了该元素，完毕
                    break;
                }
            }
        }
    }
    /*
比较v元素是否大于w元素
*/
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    /*
数组元素i和j交流方位
*/
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

时刻杂乱度为 ==O(N^2)==

二、高级排序

1、希尔排序

希尔排序是刺进排序的一种，又称“缩小增量排序”，是刺进排序算法的一种更高效的改善版别。

前面学习刺进排序的时分，咱们会发现一个很不友好的事儿，假如已排序的分组元素为{2,5,7,9,10}，未排序的分组元素为{1,8}，那么下一个待刺进元素为1，咱们需求拿着1从后往前，顺次和10,9,7,5,2进行交流方位，才能完结真正的刺进，每次交流只能和相邻的元素交流方位。那假如咱们要提高效率，直观的主意便是一次交流，能把1放到更前面的方位，比方一次交流就能把1插到2和5之间，这样一次交流1就向前走了5个方位，能够减少交流的次数，这样的需求怎么完结呢？接下来咱们来看看希尔排序的原理。

需求：

排序前：{9,1,2,5,7,4,8,6,3,5}

排序后：{1,2,3,4,5,5,6,7,8,9}

排序原理：

选定一个增长量h，按照增长量h作为数据分组的根据，对数据进行分组；
对分好组的每一组数据完结刺进排序；
减小增长量，最小减为1，重复第二步操作。

增长量h的确认：增长量h的值每一固定的规矩，咱们这儿选用以下规矩：

int h=1
    while(h<5){
        h=2h+1；//3,7
    }
//循环完毕后咱们就能够确认h的最大值；
h的减小规矩为：
    h=h/2

希尔排序的代码完结：

//排序代码
public class Shell {
    /*
对数组a中的元素进行排序
*/
    public static void sort(Comparable[] a){
        int N = a.length;
        //确认增长量h的最大值
        int h=1;
        while(h<N/2){
            h=h*2+1;
        }
        //当增长量h小于1，排序完毕
        while(h>=1){
            //找到待刺进的元素
            for (int i=h;i<N;i++){
                //a[i]便是待刺进的元素
                //把a[i]刺进到a[i-h],a[i-2h],a[i-3h]...序列中
                for (int j=i;j>=h;j-=h){
                    //a[j]便是待刺进元素，顺次和a[j-h],a[j-2h],a[j-3h]进行比较，假如a[j]小，那么
                    交流方位，假如不小于，a[j]大，则刺进完结。
                        if (greater(a[j-h],a[j])){
                            exch(a,j,j-h);
                        }else{
                            break;
                        }
                }
            }
            h/=2;
        }
    }
    /*
比较v元素是否大于w元素
*/
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    /*
数组元素i和j交流方位
*/
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
//测验代码
public class Test {
    public static void main(String[] args) {
        Integer[] a = {9,1,2,5,7,4,8,6,3,5} ;
        Shell.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

注：处理大批量数据时，希尔排序的性能高于刺进排序

2、归并排序

关于递归：界说办法时，在办法内部调用办法自身，称之为递归。它通常把一个大型杂乱的问题，层层转换为一个与原问题类似的，规模较小的问题来求解。递归战略只需求少数的程序就能够描述出解题进程所需求的多次重复计算，大大地减少了程序的代码量。

public void show(){
    System.out.println("aaaa");
    show();
}

在递归中，不能无限制的调用自己，有必要要有边界条件，能够让递归完毕，因为每一次递归调用都会在栈内存拓荒新的空间，重新履行办法，假如递归的层级太深，很容易形成栈内存溢出。

需求：

请界说一个办法，运用递归完结求N的阶乘；

剖析：
1!: 1
2!: 2*1=2*1!
3!: 3*2*1=3*2!
4!: 4*3*2*1=4*3!
...
n!: n*(n-1)*(n-2)...*2*1=n*(n-1)!
所以，假设有一个办法factorial(n)用来求n的阶乘，那么n的阶乘还能够表示为n*factorial(n-1)

代码完结：

public class Test {
    public static void main(String[] args) throws Exception {
        int result = factorial(5);
        System.out.println(result);
    }
    public static int factorial(int n){
        if (n==1){
            return 1;
        }
        return n*factorial(n-1);
    }
}

==归并排序==是建立在归并操作上的一种有效的排序算法，该算法是选用分治法的一个十分典型的运用。将已有序的子序列兼并，得到彻底有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表兼并成一个有序表，称为二路归并。

需求：

排序前：{8,4,5,7,1,3,6,2}

排序后：{1,2,3,4,5,6,7,8}

排序原理：

尽可能的一组数据拆分红两个元素持平的子组，并对每一个子组持续拆分，直到拆分后的每个子组的元素个数是1中止。
将相邻的两个子组进行兼并成一个有序的大组；
不断的重复步骤2，直到最终只要一个组中止。

归并原理：

归并排序代码完结：

//排序代码
public class Merge {
    private static Comparable[] assist;//归并所需求的辅助数组
    /*
对数组a中的元素进行排序
*/
    public static void sort(Comparable[] a) {
        assist = new Comparable[a.length];
        int lo = 0;
        int hi = a.length-1;
        sort(a, lo, hi);
    }
    /*
对数组a中从lo到hi的元素进行排序
*/
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        //对lo到mid之间的元素进行排序；
        sort(a, lo, mid);
        //对mid+1到hi之间的元素进行排序；
        sort(a, mid+1, hi);
        //对lo到mid这组数据和mid到hi这组数据进行归并
        merge(a, lo, mid, hi);
    }
    /*
对数组中，从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并
*/
    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        //lo到mid这组数据和mid+1到hi这组数据归并到辅助数组assist对应的索引处
        int i = lo;//界说一个指针，指向assist数组中开端填充数据的索引
        int p1 = lo;//界说一个指针，指向第一组数据的第一个元素
        int p2 = mid + 1;//界说一个指针，指向第二组数据的第一个元素
        //比较左面小组和右边小组中的元素巨细，哪个小，就把哪个数据填充到assist数组中
        while (p1 <= mid && p2 <= hi) {
            if (less(a[p1], a[p2])) {
                assist[i++] = a[p1++];
            } else {
                assist[i++] = a[p2++];
            }
        }
        //上面的循环完毕后，假如退出循环的条件是p1<=mid，则证明左面小组中的数据现已归并完毕，假如退出循环的条件是p2<=hi,则证明右边小组的数据现已填充完毕；
            //所以需求把未填充完毕的数据持续填充到assist中,//下面两个循环，只会履行其中的一个
            while(p1<=mid){
                assist[i++]=a[p1++];
            }
        while(p2<=hi){
            assist[i++]=a[p2++];
        }
        //到现在中止，assist数组中，从lo到hi的元素是有序的，再把数据拷贝到a数组中对应的索引处
        for (int index=lo;index<=hi;index++){
            a[index]=assist[index];
        }
    }
    /*
比较v元素是否小于w元素
*/
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    /*
数组元素i和j交流方位
*/
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
//测验代码
public class Test {
    public static void main(String[] args) throws Exception {
        Integer[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        Merge.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

归并排序的时刻杂乱度为==O(nlogn)==

注：希尔排序和归并排序在处理大批量数据时不同不是很大。

3、快速排序

快速排序是对冒泡排序的一种改善。它的基本思想是：经过一趟排序即将排序的数据分割成独立的两部分，其中一部分的一切数据都比另外一部分的一切数据都要小，然后再按此办法对这两部分数据别离进行快速排序，整个排序进程能够递归进行，以此到达整个数据变成有序序列。

需求：

排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}

排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}

排序原理：

首先设定一个分界值，经过该分界值将数组分红左右两部分；
将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左面。此刻左面部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
然后，左面和右边的数据能够独立排序。对于左面的数组数据，又能够取一个分界值，将该部分数据分红左右两部分，相同在左面放置较小值，右边放置较大值。右侧的数组数据也能够做类似处理。
重复上述进程，能够看出，这是一个递归界说。经过递归将左面部分排好序后，再递归排好右侧部分的次序。当左面和右侧两个部分的数据排完序后，整个数组的排序也就完结了。

切分原理：

把一个数组切分红两个子数组的基本思想：

找一个基准值，用两个指针别离指向数组的头部和尾部；
先从尾部向头部开端查找一个比基准值小的元素，查找到即中止，并记载指针的方位；
再从头部向尾部开端查找一个比基准值大的元素，查找到即中止，并记载指针的方位；
交流当时左面指针方位和右边指针方位的元素；
重复2,3,4步骤，直到左面指针的值大于右边指针的值中止。

快速排序代码完结：

//排序代码
public class Quick {
    public static void sort(Comparable[] a) {
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo,hi);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi<=lo){
            return;
        }
        //对a数组中，从lo到hi的元素进行切分
        int partition = partition(a, lo, hi);
        //对左面分组中的元素进行排序
        //对右边分组中的元素进行排序
        sort(a,lo,partition-1);
        sort(a,partition+1,hi);
    }
    public static int partition(Comparable[] a, int lo, int hi) {
        Comparable key=a[lo];//把最左面的元素当做基准值
        int left=lo;//界说一个左面指针，初始指向最左面的元素
        int right=hi+1;//界说一个右侧指针，初始指向左右侧的元素下一个方位
        //进行切分
        while(true){
            //先从右往左扫描，找到一个比基准值小的元素
            while(less(key,a[--right])){//循环中止，证明找到了一个比基准值小的元素
                if (right==lo){
                    break;//现已扫描到最左面了，无需持续扫描
                }
            }
            //再从左往右扫描，找一个比基准值大的元素
            while(less(a[++left],key)){//循环中止，证明找到了一个比基准值大的元素
                if (left==hi){
                    break;//现已扫描到了最右边了，无需持续扫描
                }
            }
            if (left>=right){
                //扫描完了一切元素，完毕循环
                break;
            }else{
                //交流left和right索引处的元素
                exch(a,left,right);
            }
        }
        //交流最终rigth索引处和基准值地点的索引处的值
        exch(a,lo,right);
        return right;//right便是切分的边界
    }
    /*
数组元素i和j交流方位
*/
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    /*
比较v元素是否小于w元素
*/
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
}
//测验代码
public class Test {
    public static void main(String[] args) throws Exception {
        Integer[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 8};
        Quick.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

时刻杂乱度为==O(nlogn)==

4、排序的安稳性

安稳性的界说：

数组arr中有若干元素，其中A元素和B元素持平，并且A元素在B元素前面，假如运用某种排序算法排序后，能够保证A元素仍然在B元素的前面，能够说这个该算法是安稳的。

常见排序算法的安稳性：

冒泡排序： 只要当arr[i]>arr[i+1]的时分，才会交流元素的方位，而持平的时分并不交流方位，所以冒泡排序是一种安稳排序算法。
挑选排序: 挑选排序是给每个方位挑选当时元素最小的,例如有数据{5(1)，8 ，5(2)， 2， 9 },第一遍挑选到的最小元素为2，所以5(1)会和2进行交流方位，此刻5(1)到了5(2)后边，损坏了安稳性，所以挑选排序是一种不安稳的排序算法。
刺进排序： 比较是从有序序列的结尾开端，也便是想要刺进的元素和现已有序的最大者开端比起，假如比它大则直接刺进在其后边，不然一向往前找直到找到它该刺进的方位。假如碰见一个和刺进元素持平的，那么把要刺进的元素放在持平元素的后边。所以，持平元素的前后次序没有改动，从原无序序列出去的次序便是排好序后的次序，所以刺进排序是安稳的。
希尔排序： 希尔排序是按照不同步长对元素进行刺进排序 ,虽然一次刺进排序是安稳的，不会改动相同元素的相对次序，但在不同的刺进排序进程中，相同的元素可能在各自的刺进排序中移动，最终其安稳性就会被打乱，所以希尔排序是不安稳的。
归并排序： 归并排序在归并的进程中，只要arr[i]<arr[i+1]的时分才会交流方位，假如两个元素持平则不会交流方位，所以它并不会损坏安稳性，归并排序是安稳的。
快速排序： 快速排序需求一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左面找一个比基准值大的元素，然后交流这两个元素，此刻会损坏安稳性，所以快速排序是一种不安稳的算法。

数据结构的六大排序算法详解

一、简略排序

1、Comparable接口介绍

2、冒泡排序

3、挑选排序

4、刺进排序

二、高级排序

1、希尔排序

2、归并排序

3、快速排序

4、排序的安稳性

作者信息

数据结构的六大排序算法详解

一、简略排序

1、Comparable接口介绍

2、冒泡排序

3、挑选排序

4、刺进排序

二、高级排序

1、希尔排序

2、归并排序

3、快速排序

4、排序的安稳性

相关文章

从自由职业到小公司再到港企再到国企，辛酸2022

【AI绘画】素材自己造？我的图文封面是AI创作的

去年裸辞全职做开源后，趁快过年说说这一年的经历

从斐波那契数列到动态规划

作者信息