小珍利用撲克牌來演示排序演算法已知排序過程中僅會發生左右相鄰的兩張牌互相交換位置則小珍演示的是何種排序法

小小的插入排序，大大的学问

2022年01月27日 00:00 ·  阅读 670

这是我参与2022首次更文挑战的第4天，活动详情查看：2022首次更文挑战

插入排序

贴一段搜狗百科的概述：

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

其实，插入排序的过程很像我们在斗地主时整理扑克牌时的场景，假如你现在拿到四张已经排好序的牌：

再摸到到一张7：

那么我们就会将这张7跟手里的牌进行比较，先跟9比较，再跟8比较，最后跟5比较，发现比5大，那么你就会把7放在5跟8之间。

简单来说，插入排序就是将未排序的元素一个一个插入到有序的集合中，插入的时候就像我们上面一样，从后向前扫一遍，找到合适的位置插入。

算法步骤

一般来说，插入排序都采用在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素（新元素），在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

如下图所示：

代码贴贴：

public void insert_sort(int[] nums){
    for(int i=1;i<nums.length;++i){
        //新元素
        int temp = nums[i];
        int j;
        //从后向前遍历，大于新元素的都往后移，直到遇到小于或者等于新元素的
        for(j=i;j>0 && nums[j-1] > temp;--j){
            nums[j] = nums[j-1];
        }
        //将新元素放在后面
        nums[j] = temp;
    }
}
复制代码

到这里大家就应该知道插入排序是稳定的了吧，两个相同的元素在排序的时候他们之间的相对位置是不会改变的，这是因为我们在从后往前遍历的时候，遇到相同元素就直接插入在它后面了，相对位置是没有发生变化的。

插入排序的优化

二分法插入排序

插入排序的时间复杂度是O(n^2)，空间复杂度为O(1)，那么对于这个排序算法，是否还有优化的空间呢?答案是肯定的。

我们可以发现，在插入新元素的时候，前面的序列已经是有序的了，既然如此，对于有序的序列，我们可以引入二分法，找到新元素该插入的位置，再将元素插入！

代码贴贴：

public void binaryInsertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int temp = nums[i];
        int right = i - 1;
        int left = 0;
        int mid;
        //二分法定位
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] > temp) {
                right = mid - 1;
            } else if (nums[mid] < temp) {
                left = mid + 1;
            }
        }
        // 移动数组
        for (int j = i; j > left; j--) {
            nums[j] = nums[j - 1];
        }
        // 在找到的位置插入
        nums[left] = temp;
    }
}
复制代码

希尔排序

不管是上面的直接插入排序还是二分法插入排序，我们在找到插入位置的时候，都需要将元素向后面移动，这部分的工作是最耗时的。
那有没有办法能够减少这种元素移动的消耗呢?有的，在我们的序列相对有序的情况下，插入排序的效率高，那么我们就要采取一种方式，这种方式能够让我们的数组在宏观上看是相对有序的，它就是希尔排序。
希尔排序是把数组按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。
简单来说，希尔排序就是先将整个待排序的数组分割成为若干子数组分别进行直接插入排序，待整个数组中的元素“基本有序”时，再对全体元素进行直接插入排序。

为了理解上面所说的，我们看下图，我们将数组按照增量为5进行分组：

对这五组数据分别进行直接插入排序，结果如下，可以看到，像3、5、6这些小元素都被调到前面去了，然后缩小增量，gap=5/2=2，数组被分成2组[3,1,0,9,7]，[5,6,8,4,2]。

对以上2组再分别进行直接插入排序，结果如下，此时整个数组的有序程度更进一步，再缩小增量gap=2/2=1，此时，整个数组就被分为一组了。

此时，我们的数组在宏观上上已经是基本有序了，再对其进行插入排序的时候，仅仅只需要微微调整，无需大量移动操作就可以对数组排好序了。

代码贴贴：

public static void hillSort(int []nums){
     //增量gap，并逐步缩小增量
     for(int gap=nums.length/2;gap>0;gap/=2){
         //从第gap个元素，逐个对其所在组进行直接插入排序操作
        for(int i=gap;i<nums.length;i++){
            int j = i;
            int temp = nums[j];
            if(nums[j]<nums[j-gap]){
                 while(j-gap>=0 && temp<nums[j-gap]){
                        //移动法
                        nums[j] = nums[j-gap];
                        j-=gap;
                 }
                 nums[j] = temp;
            }
        }
     }
 }
复制代码

在希尔排序中，增量的选择是非常重要的，直接影响到希尔排序的性能，一般来说最简单的增量取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。

结尾

本文介绍了插入排序，由以扑克牌的例子引出插入排序的思想，在插入排序的基础上我们引入了二分法对其进行了优化，俗称二分法插入排序。
为了减少元素移动操作，我们又引入了希尔排序，借助增量分组来达到数组的在宏观上基础有序，以便于提高插入排序的效率，但是，希尔排序确实不稳定的。因为在分组插入排序时，相同元素的相对位置可能会发生改变。
值得注意的是，希尔排序的增量选择是希尔排序的关键，希尔排序的时间复杂度为O(n^1.3)-O(n^2),在一些极端情况下，希尔排序的性能甚至比插入排序更慢，例如在对数组[2,1,5,3,7,6,9,8]进行希尔排序，并且开始以4作为增量直到1，会发现每组内的元素没有交换，这样不仅没有减少直接插入排序的工作量，反而白白增加了分组操作的成本，为了尽量避免这样的极端情况，人们提出更为严谨的增量方式，最具代表性的有Hibbard增量和Sedgewick增量，感兴趣的朋友可以自行了解。