插入排序

1. 前言

本节内容是排序算法系列之一：插入排序，主要讲解了插入排序的主体思路，选取了一个待排序的数字列表对插入排序算法进行了演示，给出了插入排序算法的 Java 代码实现，帮助大家可以更好地理解插入排序算法。

2. 什么是插入排序？

插入排序（Insert Sort），是计算机科学与技术领域中较为简单的一种排序算法。

顾名思义，插入排序是通过不断插入待排序的元素完成整个排序过程。插入排序是一种很简单的排序方式，基本思想就是将一个元素插入到已经排序好的序列中，从而形成一个新的有序序列。它重复地选择未排序的元素，将其插入已经排序好的序列中，直到没有待排序元素时，整个排序过程完成。

插入排序的工作方式就像大家打扑克牌时抓牌一样。开始时，我们手上是没有牌的，依次从桌面上面抓取扑克牌，然后插入自己手中已有扑克牌的位置中，只是插入的时候我们按照一定的顺序将它插入到合适的位置中。

3. 插入排序过程

在介绍完插入排序之后，我们一起来看一下插入排序的实现步骤具体是什么样的吧。同样的，和之前介绍冒泡排序时一样，这里我们假设待排序的序列为 [9,2,11,7,12,5] ，我们按照从小到大的序列进行排序。

3.1 算法步骤

1. 步骤 1：

选择待排序序列中的第一个元素作为一个有序序列，将剩余元素看成是一个未排序序列；

2. 步骤 2：

依次从未排序序列中选择一个元素，与已排序序列中的元素依次比较，将其插入到合适的位置。

其实，上面的步骤 2 每执行一次，都会有一个新的排序好的序列形成，并且这个新的排序好的序列在依次变大，直至整个排序工作完成。接下来，让我们用上面的待排序数字序列 [9,2,11,7,12,5] 进行整个算法步骤的排序演示工作。

3.2 算法演示

按照 2.1 节的排序步骤，首先我们会选择出待排序队列中的第一个元素作为一个已经排序好的序列，将剩余元素作为一个未排序好的序列。所以开始我们将待排序序列 [9,2,11,7,12,5] 分成了排序好的序列 [9] 和未排序序列 [2,11,7,12,5]，如下：

[9,2,11,7,12,5]  --> [9];[2,11,7,12,5]   //[9]排序好的序列，[2,11,7,12,5]未排序序列，中间用;分开

接着，我们调用 2.1 中的步骤 2，依次从未排序序列中选择一个元素，与已排序序列中的元素依次比较，将其插入到合适的位置。整个过程如下：

[9];[2,11,7,12,5]   -->  [2,9];[11,7,12,5]	 //选择未排序元素2，插入排序好的序列[9]形成新的排序好序列[2,9]
[2,9];[11,7,12,5]   -->  [2,9,11];[7,12,5]	 //选择未排序元素11，插入排序好的序列[2,9]形成新的排序好序列[2,9,11]
[2,9,11];[7,12,5]   -->  [2,7,9,11];[12,5]	 //选择未排序元素7，插入排序好的序列[2,9,11]形成新的排序好序列[2,7,9,11]
[2,7,9,11];[12,5]   -->  [2,7,9,11,12];[5]	 //选择未排序元素12，插入排序好的序列[2,7,9,11]形成新的排序好序列[2,7,9,11,12]
[2,7,9,11,12];[5]   -->  [2,5,7,9,11,12];[]	 //选择未排序元素5，插入排序好的序列[2,7,9,11,12]形成新的排序好序列[2,5,7,9,11,12]

步骤 2 会依次从未排序序列中选择一个元素，按照如上过程一样，将待排序元素插入到已经排序好的序列中，形成一个新的排序好的序列，减少待排序元素的数量，直至整个排序工作完成。

Tips: 步骤 2 每次执行的时候，都是需要将待排序元素与已经排序好的序列中的每个元素进行依次比较，才能找到待排序元素的插入位置。例如：[2,9,11] ; [7,12,5] --> [2,7,9,11] ; [12,5]，在将待排序元素 7 插入到排序好的序列 [2,9,11] 中时，需要依次将 7 和序列 [2,9,11] 中的元素比较，发现 7>2，继续比较下一个，7<9，所以 7 应该插入到排序好的序列 [2,9,11] 的 2 和 9 之间。

从上面的示例可以看出，其实整个插入排序的过程，会将原来的待排序序列分成已经排序好的序列和尚未排序的序列，从尚未排序的序列中依次选择元素，插入到排序好的序列中。

4. Java 代码实现

在说明插入排序的整个过程之后，接下来，我们看看如何用 Java 代码实现插入排序算法。

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        //初始化需要排序的数组
        int array[] = {9, 2, 11, 7, 12, 5};

        //初始化一个与待排序数组大小相同的数组，用来存放排序好的序列
        int sortArray[] = new int[array.length];

        //步骤1：待排序数组中选择第一个元素作为已经排序好的元素（数组的下标0表示第一个元素）
        sortArray[0] = array[0];

        //步骤2：依次遍历未排序的元素，将其插入已排序序列中
        for (int i = 1; i < array.length; i++) {
            //待排序元素
            int temp = array[i];
            //记录待排序元素需要插入已排序数组中的位置
            int index = i;
            //从已排序好的数组右边依次遍历数组，直到找到待排序元素需要插入的位置
            while(  index > 0  && temp < sortArray[index-1] ){
                sortArray[index] = sortArray[index-1];
                index--;
            }
            //插入待排序元素
            sortArray[index] = temp;
        }

        //打印出排序好的序列
        System.out.println(Arrays.toString(sortArray));
    }

}

运行结果如下：

[2, 5, 7, 9, 11, 12]

代码中的第 7 行初始化一个需要排序的数组，第 10 行初始化一个与待排序数组大小相同的数组，用来存放排序好的序列。第 13 行将待排序数组中选择第一个元素作为已经排序好的元素，放入排序好的数组中。第 16 行是外层循环，不断地重复排序工作，将未排序的元素插入到排序好的序列中。第 22 行是内部的 while 循环，找到待排序元素需要插入的排序好的数组中的位置，实现插入排序。第 31 行打印出排序好的数组。

5. 小结

本节主要学习了插入排序算法，本节内容需要熟悉插入排序的算法流程，知道插入排序算法的实现思路，可以自己用代码实现插入排序算法。在学完本节课程之后，我们已经完成了排序算法中的冒泡排序、插入排序的学习。