[数据结构与算法]【JavaSE|数据结构】排序算法之冒泡排序，选择排序，插入排序与希尔排序

??前面的话??

本篇文章带大家认识排序算法——冒泡排序，选择排序，插入排序与希尔排序，其中冒泡排序，选择排序，插入排序是基础的排序算法，希尔排序是插入排序的优化，四种排序算法全部都是基于比较的排序算法，本文将以图解动图的方式描述算法实现过程，实现代码为java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏??留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年2月21日🌴
??坚持和努力一定能换来诗与远方！
💭参考书籍：📚《Java核心技术》，📚《Java编程思想》，📚《数据结构》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🙏作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

题外话：排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作，排序算法是面试当中高频的考点，并且许多题都有用到排序算法的思路。

1.排序

1.1排序

排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。一般情况下（包括后文），如果提到排序，通常指的是排升序（非降序）。通常意义上的排序，都是指的原地排序(in place sort)。

1.2排序的稳定性

两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。

对于基于排序的排序算法，如果一个排序中基于“跳跃式”元素交换（或插入）进行排序，则该排序大概率（不是一定，本质还是要看相同元素值的相对位置是否改变）是不稳定的，对于一种稳定的排序算法，可以实现成不稳定的，而不稳定的排序算法，是无法实现成稳定的形式。

基于比较的常见排序算法有：冒泡排序，选择排序，插入排序，折半插入排序，希尔排序，堆排序，归并排序，快速排序等；基于非比较的常见排序算法有：计数排序，基数排序，桶排序等。

2.冒泡排序

2.1排序算法

从第二个元素开始，将该元素与前一个元素比较，如果前一个元素比较大，则交换。直到最后一个元素为最大元素，这一过程称为一趟冒泡排序。每进行一趟冒泡排序，缩小一次右侧区间，因为每进行一趟冒泡排序就有一个元素“归位”。
例如这样一组数据：[18, 16, 12, 23, 48, 24, 2, 32, 6, 1]

自定义交换数组元素方法：

    public void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

根据上述基本思路我们可以得到冒泡排序的代码：

    /**
     * 冒泡排序
     * @param array 排序对象
     */
    //优化前
    public void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {    //排序趟数
            for (int j = 1; j < array.length - i; j++) {
                //如果j所有处元素小于j-1索引处元素，则交换，否则不交换
                if (array[j] < array[j - 1]) {
                    swap(array, j, j-1);
                }
            }
        }
    }

但是会有一个问题，那就是如果数组已经有序了呢？这时候不需要再进行冒泡排序了，所以我们可以进行一点点优化，基本思路就是当遇到一趟排序时并没有发生元素交换，这时候就说明数组已经有序了，下一趟就不用排了，所以在交换过程中加上一个“标记”，这样就可以根据这个标记来确定后续是否需要继续冒泡排序。

    //优化后
    public void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {    //排序趟数
            boolean flag = false;                       //标记
            for (int j = 1; j < array.length - i; j++) {
                //如果j所有处元素小于j-1索引处元素，则交换，否则不交换
                if (array[j] < array[j - 1]) {
                    swap(array, j, j-1);
                    flag = true;                        //发生交换将标记置为真
                }
            }
            if (!flag) break;                           //一趟冒泡排序后flag为false说明数组已经有序了
        }
    }

2.2性能分析

最好情况：数组有序，时间复杂度O(N)。

3.选择排序

3.1排序算法

选择排序的思路很简单，从0下标开始，不妨设此处元素下标为i， 找到i后面（包括i处下标）最小元素的下标，然后将最小元素与i处的元素交换，最后i++，这样数组就会呈升序排列，如果要降序就找最大值交换就可以了。简单说，就是找到最小元素将它排在最前面， 然后继续选择出此元素的最小值排在该元素后面，这样遍历完数组后，数组也变得有序了。
还是以[18, 16, 12, 23, 48, 24, 2, 32, 6, 1]为例。

动图演示：

选择排序代码实现：

    /**
     * 选择排序
     * @param array 待排序序列
     */
    public void selectSort(int[] array) {
        int minIndex = 0;                                    //存放最小元素的下标
        for (int i = 0; i < array.length - 1; i++) {
            minIndex = i;                                   //默认为i下标
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;                           //获取i下标后面更小元素的下标
                }
            }
            swap(array, i, minIndex);                       //交换
        }
    }

3.2性能分析

4.插入排序

4.1直接插入排序

4.1.1排序算法

从第二个元素开始，不妨将这个元素的下标设为i， 并使用变量insert储存该元素，设下标index，默认第一个值为i-1。
如果下标index对应元素比insert大，则将则向右移动一步（即将index+1位置储存该元素），并将index--，直到index<0或者index对应元素小于insert，此时将insert储存至index+1处。就能将insert插入到一个合适的位置，使得前i+1个元素有序，对所有元素完成插入后，数组将升序排列，如果要降序，则插入的时候要把大的元素移动到数组前面，思路是一样的。

直接插入排序实现代码：

    /**
     * 直接插入排序
     * @param array 待排序对象
     */
    public void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int insert = array[i];                      //待插入元素
            int index = i - 1;                          //待插入元素前一个元素下标
            while (index >= 0) {
                if (array[index] > insert) {
                    array[index + 1] = array[index];          //在数组下标合法范围内，比较insert与index位置元素大小，如果index位置元素更大则将此元素放入index+1位置，index--
                    index--;
                }else {
                    break;                                  //否则结束插入
                }
            }
            array[index+1] = insert;                          //将insert插入index+1位置处
        }
    }

4.1.2性能分析

最好情况：数组有序，O(N)。直接插入排序有一个特点，越趋于有序，排序速度越快，根据此特点对数组进行分组多次直接插入排序，能够大大提高排序的效率，这种方法也就是后面的希尔排序。

4.2希尔排序

4.2.1排序算法

希尔排序（Shell’s Sort）又称"缩小增量排序"（Diminishing Increment Sort），它也是一种属插入排序类的方法，但在时间效率上较前述几种排序方法有较大的改进。
假如有15个元素需要排序，首先将这15个元素分为5组，对每组分别进行直接插入排序，再分为3组，并对每组分别进行直接插入排序，最后分为1组，进行直接插入排序，从理论上来说比一次直接插入排序要快。其实这个分组并不是唯一的，只需要满足分组数要依次递减并且最后一次排序必须分一组进行排，但是提高速度的快慢与怎么分，分几组息息相关，严蔚敏所著的《数据结构》对希尔排序的效率问题是这样表示的：


所以就目前来说，希尔排序时间复杂度能够达到$O(N^{3/2})$，本文不深入探究希尔排序的增量序列，就按照每次对分组数折半作为增量序列，虽然不是最优解，但是毋庸置疑肯定是要比一次直接插入排序要快的。

举个例子，有1万个数据需要排序，直接插入排序的时间复杂度高达1亿，如果每次排100个数分100组，它所需时间复杂度为100100100等于100万，由于每次直接插入排序后，数据会越来越趋于有序，所以最终的时间复杂度肯定要比1亿要小。

除了组数的减少增量序列，还有如何去对数据进行划分也会影响时间复杂度，比如对15个数进行分组，最常见的思路就是每相邻五个作为一组，但是这样划分并不是非常合适的，科学将则想到间隔划分，就是对下标0,5,10作为一组，剩下的为1,6,11，2,7,12，3,8,13，4,9,14，发现这样分组要优于平均连续分组。

还是举一个实例吧，还是这个数组：[18, 16, 12, 23, 48, 24, 2, 32, 6, 1]
按照折半增量序列来分组，使用间隔的方式来划分，那么组数依次为5,2,1。

使用间隔划分的方式明显可以看出越小的元素基本上在前面，越大的元素基本上在后面，这样使数组越来越趋于有序，直接插入排序也会越来越快。

希尔排序代码实现：

    /**
     * 希尔排序
     * @param array 待排序序列
     * @param gap 组数
     */
    public void shell(int[] array,int gap) {
        int insert = 0;
        for (int i = gap; i < array.length; i++) {
            insert = array[i];
            int j = i - gap;
            while (j >= 0) {
                if (array[j] > insert) {
                    array[j + gap] = array[j];
                    j -= gap;
                } else {
                    break;
                }
            }
            array[j + gap] = insert;
        }
    }

    public void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);//保证最后是1组
    }

4.2.2性能分析

希尔排序是直接插入排序的一种优化。