阅读:0       作者:严长生

插入排序算法(java实现详解版)

插入排序分为两种,直接插入排序二分插入排序,本节我们只介绍直接插入排序。这两种插入排序实际上都是插入排序,唯一的不同就是插入的方式不一样。
  • 插入排序就是往数列里面插入数据元素。一般我们认为插入排序就是往一个已经排好序的待排序的数列中插入一个数,使得插入这个数之后,数列仍然有序。
  • 二分插入排序也是用了分治法的思想去排序的。实际上二分就是使用二分查找来找到这个插入的位置,剩余的插入的思想其实和直接插入排序一样。

所以要完成插入排序,就需要找到这个待插入元素的位置。下面我们一起看看插入排序的具体操作原理。

插入排序的原理

插入排序实际上把待排序的数列分为了两部分,一部分已排好序,另一部分待排序。我们下面还是以一组实际数据为例进行讲解。假设待排序的数列为 63、88、34、99、38、55、9,首先我们将数列储存为如图 1 所示。


图 1 待排序的数列的初始状态

这时,全部数列都为待排序部分,我们开始一点点地进行插入排序。

首先把 63 拿出来,这是第 1 个元素,不需要排序。这时,已排好序的部分已经有一个元素了,就是 63,而剩余的元素为待排序的部分。

接着我们把 88 拿出来,与前面的元素相比较,发现比 63 大,符合我们把数列小到大排序的想法,无须交换。这时已排好序的部分又增加了一个新成员,而待排序部分相应地少了一个元素。

之后我们看 34,比前面的元素 88 比较,发现比 88 小,我们把 34 拿出来,让它在外面等一下,把88向后移动一位,此时数组的情况如图 2 所示。


图 2 待排序的数列的状态,将 88 向后移动一位

接下来我们继续向前比较,直到比较到第 1 个元素为止。这时发现 34 仍然比 63 小,继续把 63 向后移动,这时的状态如图 3 所示。


图 3 待排序的数列的状态,将 63 向后移动一位

现在发现已经比较到第 1 个元素了,第 1 个位置的 63 元素需要移动,所以第 1 个位置空出来了,那就把拿出来的 34 放到第 1 个位置上,这时数列状态变为 34、63、88、99、38、55、9。

现在,已排好序的数列部分为 34、63、88,剩余的后面部分为待排序部分。我们继续看后面的元素,该处理 99 了,与前 1 个元素比较,发现比 88 大,由于前面的部分已排好序,所以 88 就是前面数列中最大的,99 比 88 大,肯定也比前面的所有元素都大,不用继续比较了,可以直接把 99 加入前面的已排好序的部分了。

接下来处理 38,与前 1 个元素比较,发现比 99 小,于是把 38 拿出来,将 99 向后移动,这时的待排序的数列的状态如图 4 所示。


图 4 待排序的数列的状态,将 99 向后移动一位

接着继续用 38 与 88 比较,发现比 88 小,88 继续后移一位;继续与 63 比较,发现比 63 小,63 也后移一位,这时的数组状态如图 5 所示。


图 5 当前的待排序的数列状态

此时继续用 38 与 34 比较,发现比 34 大,不管 34 前面有没有元素,都不用继续比较了,可以直接把 38 放在那个空位上。此时的数组状态变为 34、38、63、88、99、55、9。

后面就是分别处理 55 和 9 这两个元素了。通过上面的几次移动与比较,我们应该可以自己完成对这两个元素的插入了。最后当待排序的部分已经没有了时,整个数列就已经完成所有的排序操作了。

接下来我们总结一下直接插入排序的整个执行过程。
  1. 首先需要明确待排序的数列由两部分组成,一部分是已排好序的部分,另一部分是待排序的部分。
  2. 接着我们每次选择待排序的部分的第 1 个元素,分别与前面的元素进行比较。当大于前面的元素时,可以直接进入已排好序的部分;当小于前面的元素时,需要把这个元素拿出来,将前面的元素后移一位,继续与前面的元素相比,直到比较完数组的第 1 个元素或者出现一个元素小于我们拿出来的这个元素,这时停止比较、移动,直接把这个元素放到当时的空位上。
  3. 一直重复步骤 2,当待排序的部分已经没有元素可进行插入时,停止操作,当前的数列为已排好序的数列。

插入排序的实现

插入排序的实现代码已经可以写出来了。首先外层肯定有个大循环,循环这个待排序的部分的数列,内层是分别与前 1 个元素进行比较、移动,直到找到位置进行插入为止。

下面我们看看插入排序的代码实现。
public class InsertSort {
    private int[] array;
    public InsertSort(int[] array) {
        this.array = array;
    }
    public void sort() {
        if (array == null) {
            throw new RuntimeException("array is null");
        }
        int length = array.length;
        if (length > 0) {
            for (int i = 1; i < length; i++) {
                int temp = array[i];
                int j = i;
                for (; j > 0 && array[j - 1] > temp; j--) {
                    array[j] = array[j - 1];
                }
                array[j] = temp;
            }
        }
    }
    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}
下面是测试代码。
public class SortTest {
    public static void main(String[] args) {
        testInsertSort();
    }
    /**
     * 插入排序
     */
    private static void testInsertSort() {
        int[] array = {5, 9, 1, 9, 5, 3, 7, 6, 1};
        InsertSort insertSort = new InsertSort(array);
        insertSort.sort();
        insertSort.print();
    }
}
和自己写的代码对照一下,你是否完美地完成这个算法了呢?

插入排序的特点及性能

插入排序的操作很简单,而且我们通过上面的实例及原理可以知道,插入排序在数列近似有序时,效率会比较高,因为这样会减少比较和移动的次数。

插入排序的时间复杂度是 O(n2),我们会发现这个实现是个双重嵌套循环,外层执行n遍,内层在最坏的情况下执行 n 遍,而且除了比较操作还有移动操作。最好的情况是数列近似有序,这时一部分内层循环只需要比较及移动较少的次数即可完成排序。如果数列本身已经排好序,那么插入排序也可以达到线性时间复杂度及 O(n),所以我们应该明确地认识到,使用插入排序算法进行排序时,数列越近似有序,性能就越高。

插入排序的空间复杂度是 O(1),是常量级的,由于在采用插入排序时,我们只需要使用一个额外的空间来存储这个“拿出来”的元素,所以插入排序只需要额外的一个空间去做排序,这是常量级的空间消耗。

插入排序是稳定的,由于是数组内部自己排序,把后面的部分按前后顺序一点点地比较、移动,可以保持相对顺序不变,所以插入排序是稳定的排序算法。

插入排序的适用场景

插入排序的性能并不是很好,和冒泡排序也算是“难兄难弟”了。但插入排序也有一个好处就是所占用的空间很少,只有一个存储临时变量的额外空间就够了。

插入排序由于其时间复杂度并不是很好,所以很少会被单独使用。在所有的基本排序算法中,在一般情况下我们可以直接选择快速排序,因为这个排序算法已经够用了。

由于在数列近似有序时,性能会比较好,而且对于元素较少的情况,时间复杂度就算是 O(n2) 也不会消耗太多的性能,所以插入排序并非一无是处。

前面提到,在快速排序的分区规模达到一定的值比如 10 时,我们会改用插入排序算法去排序那个分区的数据。而快速排序的最后的数据往往是近似有序的,所以使用快速排序的性能并不一定会有多好,这时使用插入排序的实际性能往往会更好些。所以很多编程语言在内部对快速排序的实现也是在分区的元素数量达到了一定小的规模时,改用插入排序对分区的数据元素进行排序操作。