十大排序算法 -- 插入排序｜8 月更文挑战

阿粤Ayue

关注

发布于: 2 小时前

插入排序

当我们在玩扑克牌的时候，总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。

插入排序是指在待排序的元素中，假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第 n 个数的这个序列也是排好顺序的。

对于未排序数据（一般取数组的二个元素，把第一个元素当做有序数组），在已排序序列中从左往右扫描，找到相应位置并插入。
为了给要插入的元素腾出空间，需要将插入位置之后的已排序元素在都向后移动一位。

代码实现

对下面数组实现排序：{15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}

动图演示

代码实现

public class InsertionSort {
    public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1};
    public static int[] sort(int[] array) {        if (array.length == 0) {            return array;        }        //待排序数据，改数据之前的已被排序        int current;        for (int i = 0; i < array.length - 1; i++) {            //已被排序数据的索引            int index = i;            current = array[index + 1];            //将当前元素后移一位            while (index >= 0 && current < array[index]) {                array[index + 1] = array[index];                index--;            }            //插入            array[index + 1] = current;        }        return array;    }

    public static void print(int[] array) {        for (int i : array) {            System.out.print(i + "  ");        }        System.out.println("");    }
    public static void main(String[] args) {        print(ARRAY);        System.out.println("============================================");        print(sort(ARRAY));    }}

复制代码

时间复杂度

在上面图示中，第一趟循环比较一次，第二趟循环两次，依次类推，则最后一趟比较 n-1 次：

1 + 2 + 3 +… + n-1 = n*(n-1)/2

复制代码

也就是说，在最坏的情况下（逆序），比较的时间复杂度为 O(n^2)

在最优的情况下，即 while 循坏总是假的，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 n-1 次，时间复杂度为 O(n)。

算法稳定性

在比较的时候，过两个数相等的话，不会进行移动，前后两个数的次序不会发生改变，所以插入排序是稳定的。

发布于: 2 小时前阅读数: 4

原文链接:【http://xie.infoq.cn/article/dcb15f98e86189ab6c5710a20】。文章转载请联系作者。

阿粤Ayue

关注

微信搜：Javatv 2019.10.16 加入

秘密基地：javatv.net

发布

暂无评论

创作场景

十大排序算法 -- 插入排序｜8 月更文挑战

插入排序

代码实现

时间复杂度

算法稳定性

阿粤Ayue

评论