当前位置：网站首页>【八大排序①】插入排序（直接插入排序、希尔排序）

【八大排序①】插入排序（直接插入排序、希尔排序）

2022-07-02 00:43:00 【Living_Amethyst】

说在前面

一、直接插入排序（Straight Insertion Sort）

直接插入排序的算法思想
具体编写代码时

【直接插入排序的特性总结】

直接插入排序的复杂度分析
直接插入排序的稳定性分析
直接插入排序的使用场景

二、希尔排序（Shell Sort）

希尔排序法的基本思想
希尔排序的特性总结：
代码实现

【希尔排序的特性总结】

希尔排序的复杂度
希尔排序的稳定性

说在前面

关于排序，相信大家一定不陌生，在生活中我们见过许多排序，比如在购物网站搜索时，有根据价格排序、根据好评度排序、根据销量排序，我们根据关键字使内容具有一定的顺序，这便是排序。

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

排序的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内排序与外排序
内排序：在排序整个过程中，待排序的所有记录全部被放置在内存中。
外排序：由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行

排序主要为基于比较的排序和不基于比较的排序

上图的7中排序都是基于比较的排序

一、直接插入排序（Straight Insertion Sort）

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想。

直接插入排序的算法思想

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

我们用一张图来领略一下直接插入排序算法的思想

具体编写代码时

我们定义一个 i 和 j，将数组按升序排序，现在我们搭配着图来看代码

如图所示就是大概执行流程

/**
     * 直接插入排序
     * 时间复杂度 O(n)
     * 使用场景：当数据量小，并且已经趋于有序的时候
     * @param array
     */
    public static void insertSort(int[] array){
        for(int i = 1;i< array.length;i++){
            int tmp = array[i];
            int j = i-1;
            for(; j >= 0; j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

【直接插入排序的特性总结】

直接插入排序的复杂度分析

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

最好情况：要排序的表本身就是有序的，复杂度O(n)
最坏情况：要排序的表是逆序的，复杂度O(n^2)

空间复杂度：O(1)

直接插入排序的稳定性分析

是稳定的

我们发现

这里如果是 >= ，那么就是不稳定的

为什么说它的实质是稳定的呢？

如果本身就是一个稳定的排序，我们可以把它实现为不稳定的排序

但如果本身不是一个稳定的排序，那么就不可能变成稳定的排序

直接插入排序的使用场景

当数据量小，并且已经趋于有序的时候

二、希尔排序（Shell Sort）

引言：我们知道，优秀排序算法的首要条件就是速度，人们想了许多办法来提高排序的速度，在很长的时间里，众人发现尽管各种排序算法花样繁多，但时间复杂度都是O(n^2)，但终于有一天希尔排序诞生了，希尔排序是D.L.Shell于1959年提出来的一种排序算法，是突破O(n^2)这个时间复杂度的第一批算法之一

希尔排序法又称缩小增量法。

希尔排序法的基本思想

先选定一个整数，把待排序文件中所有记录分成gap个组
所有距离为gap的记录分在同一组内，并对每一组内的记录进行直接插入排序。
然后，取另一个新的gap，重复上述分组和排序的工作。
当到达gap=1时，所有记录在统一组内排好序

我们怎么通过代码实现呢，需要定义一个 i 和 j

i = gap；
j = i - gap；

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

代码实现

 public static void shell(int[] array,int gap){
        for(int i = gap;i< array.length;i++){
            int tmp = array[i];
            int j = i-gap;
            for(; j >= 0; j -= gap){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            shell(array,gap);
            gap/=2;
        }
        shell(array,1);
    }