你应该知道的常用排序算法之插入排序

人生有涯,学海无涯

前面跟大家分享的排序算法之快速排序,今天跟大家分享另外一个排序算法——插入排序。插入排序可能大家在平时真正用到地方不多,但是也会用到,而且有一个场景我想大家一定经历过,那就打扑克牌。想想我们在抓牌的时候,是不是随着拿到一张张的扑克牌,然后按照顺序插入我们左手呢(或者右手上)?这其实就是插入排序,通过依次比较前一个数字的大小,将需要排序的数字插到最适合的位置,下面我们一起看下吧。

01、插入排序

我们先看看维基百科的解释:

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

02、算法思想

插入排序的算法思想是通过构建有序序列,对未排序的数据从有序队列中依次进行比较,找到相应的位置进行插入。注意,如果当前位置不满足的情况下是需要将该位置的元素进行后移,以便腾出位置。

插入排序算法的实现大致分成三步

  1. 获取待插入的元素:
  2. 将待插入的元素与前一个元素进行比较;
  3. 如果当前元素与待插入元素大则将当前元素进行后移,再依次比较。

03、算法实现

/**
 * <br>
 * <b>Function:</b><br>
 * <b>Author:</b>@author 子悠<br>
 * <b>Date:</b>2019-09-25 00:24<br>
 * <b>Desc:</b>无<br>
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
        insertSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    /**
     * 插入排序
     *
     * @param array 待排序数组
     */
    public static void insertSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //待插入的元素
            int needInsert = array[i];
            //开始比较的索引
            int index = i - 1;
            while (index >= 0 && array[index] > needInsert) {
                //将该位置的元素进行后移
                array[index + 1] = array[index];
                //再比较该位置前一个元素
                index--;
            }
            //当前位置满足条件
            array[index + 1] = needInsert;
        }
    }
}

运行结果:

从上面的代码我们可以看到,相对于快速排序,插入排序还是比较简单的,而且理解起来也相对容易,代码中已经增加了详细的注释,相信大家都能理解。注意的点就是每次在比较完之后,对于不满足的元素,我们需要进行一个后移,这个才能给待插入的元素在数组前面腾出空间。也就是代码的 array[index + 1] = array[index]; 这一行。

插入排序算法的最好时间复杂度,是序列本身就已经有序的情况下,是 O(n),最坏的时间复杂度是 O(n^2),平均时间复杂度也是 O(n^2)。由于没有申请额外的空间,所以空间复杂度为 O(1)。

插入排序算法在数据量不是很大的时候还是比较快速好用的,但是如果数据量很大就不建议采用插入排序了,可以采用变种的二分查找,有机会再给大家介绍,一般数据不超过千的时候都是可以使用的。

04、总结

这篇文章简单给大家介绍了一下插入排序的思想和实现,排序算法是大家日常工作和学习不可避免要学习的知识,我们《Java 极客技术》也会在后续的文章中慢慢的给大家分享很多优质的,算法和数据结构的文章,便于大家学习和成长。最后欢迎大家到我们《Java 极客技术》知识星球中一起学习和进步,扫描下放二维码还有优惠,我们在知识星球中等你。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章