算法入门教程-插入排序

上节我们学习了选择排序算法,本节我们继续学习相关剩余算法如我们本节要学习的插入排序,直接入正题,先来介绍下什么是插入排序?

插入排序介绍

插入排序也是基于内存操作的,是对想要排序的元素已插入的方式寻找到该元素的位置已达到排序的效果.

看着很难以理解,通过一个例子来看看,如图:

插入排序图.png

上图中初始状态我们可以看成是一个数组R,其中R[0]~R[5]表示对应值的下标索引,其中该数组为R= {17,3,25,14,20,9},接着我们来看一下这个过程

• 说明:
• 1 我们可以将R数组看成是一个有序列列{17}和无序列{3,25,14,20,9},我们要做到是将.
• 无序列中的值往有序列{17}中插入,至于规则自己定.'
• 2 我这里就按照上图中的来说插入的时候按照从小到大插入即可
• 过程:
• 第一次插入的时候,将无序列中的下标为1的值(3)插入有序列中{17}中,发现要插入的值小于有序列中的原先的值,首先将原先有序列中的值往后移动一位,接着将3插入空出来的位置即可.
• 第二次插入的时候是将数组R中的R[2]也就是值为25,通过判断发现25大于有序列中的3和17,故它的位置不变,这里是一种巧合的场景.
• 第三次插入的时候,将数组R中的R[3]插入到有序列表{3,17,25}中通过比较14大于3小于17即插入到3和17之间即可
• 第四次和第五次重复上述过程即可

这就是上图中插入排序的过程,通过上图的过程我们来总结下插入排序的思想:

• 按照上述过程得到,我们可以将一个待排序的元素看成是一个有序列表和无序列表.
• 首先开始的时候有序列表中只有一个元素(所以它一定是有序的),无序列表中有n-1个元素
• 在排序的过程中,每次从无序列表中取出第一个元素,把它的排序号依次跟有序列表中的进行比较,然后将它插入到有序列表中的适当位置,使之成为新的有序列表.

知道了它的排序思想,我们通过代码来完成该过程

代码实现

假设我这里有一个待排序的数组元素集合arr={101,34,119,1},需要进行排序,我们来看过程

• 第一次的排序代码实现

//逐步推导过程
    //{101,34,119,1} -> 首先以{101}为有序列表,以{4,119,1}为无序列表
    //将无序列表中的数往有序列表中添加
    //定义待插入的数和索引下标
    int insertVal = arr[1]; //这里也就是34
    int insertIndex = 1 - 1; //arr[1]前面数的下标

    //简单说明:
    //1. insertIndex>=0 其主要的目的是为了防止在插入时候为了约束越界
    //2. insertVal < arr[insertIndex]表示待插入的数还没有找到插入的位置如: 34 < arr[0] =101
    //3. 需要将 arr[insertIndex]往后移动
    while (insertIndex >= 0 && insertVal < arr[insertIndex]) {

        arr[insertIndex + 1] = arr[insertIndex]; //此时的数组为{101,101,119,1}
        insertIndex--;
    }
    //当退出while循环时,说明插入的位置找到,需要 insertIndex +1 如: 34改为 134
        arr[insertIndex + 1] = insertVal;
    System.out.println("第一轮插入后的结果为:");
    System.out.println(Arrays.toString(arr));

我们先来猜测下结果,我猜测第一次排序过后的数组为{34,101,119,1},多说无益,来看测试结果:

插入排序第一轮结果图.png

从上述结果来看我们的猜测是正确的,接着看

• 第二次的排序过程:

   //定义待插入的数和索引下标
     insertVal = arr[2]; //这里也就是119
     insertIndex = 2-1; //arr[2]前面数的下标
    //简单说明:
    //1. insertIndex>=0 其主要的目的是为了防止在插入时候为了约束越界
    //2. insertVal < arr[insertIndex]表示待插入的数还没有找到插入的位置如: 34 < arr[] =101
    //3. 需要将 arr[insertIndex]往后移动
    while (insertIndex >=0 && insertVal < arr[insertIndex]){

        arr[insertIndex +1] = arr[insertIndex]; //此时的数组为{101,101,119,1}
        insertIndex --;
    }
    //当退出while循环时,说明插入的位置找到,需要 insertIndex +1 如: 34改为 134
    arr[insertIndex + 1] = insertVal;
    System.out.println("第二轮插入后的结果为:");
    System.out.println(Arrays.toString(arr));

不猜了,直接看结果图:

第二轮结果图.png

-第三次过程:

//定义待插入的数和索引下标
    insertVal = arr[3]; //这里也就是119
    insertIndex = 3-1; //arr[2]前面数的下标
    //简单说明:
    //1. insertIndex>=0 其主要的目的是为了防止在插入时候为了约束越界
    //2. insertVal < arr[insertIndex]表示待插入的数还没有找到插入的位置如: 34 < arr[] =101
    //3. 需要将 arr[insertIndex]往后移动
    while (insertIndex >=0 && insertVal < arr[insertIndex]){

        arr[insertIndex +1] = arr[insertIndex]; //此时的数组为{101,101,119,1}
        insertIndex --;
    }
    //当退出while循环时,说明插入的位置找到,需要 insertIndex +1 如: 34改为 134
    arr[insertIndex + 1] = insertVal;
    System.out.println("第三轮插入后的结果为:");
    System.out.println(Arrays.toString(arr));

来看测试结果:

第三轮测试结果图.png

通过上述过程我们完成了该元素的排序过程,我们来封装下代码:

//插入排序方法封装
public static void insertSort(int [] arr){
        int insertVal = 0;
        int insertIndex = 0;
    for (int i = 1; i <arr.length; i++) {
        //逐步推导过程
        //{101,34,119,1} -> 首先以{101}为有序列表,以{4,119,1}为无序列表
        //将无序列表中的数往有序列表中添加
        //定义待插入的数和索引下标
         insertVal = arr[i]; //这里也就是34
         insertIndex = i - 1; //arr[1]前面数的下标

        //简单说明:
        //1. insertIndex>=0 其主要的目的是为了防止在插入时候为了约束越界
        //2. insertVal < arr[insertIndex]表示待插入的数还没有找到插入的位置如: 34 < arr[0] =101
        //3. 需要将 arr[insertIndex]往后移动
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {

            arr[insertIndex + 1] = arr[insertIndex]; //此时的数组为{101,101,119,1}
            insertIndex--;
        }
        //当退出while循环时,说明插入的位置找到,需要 insertIndex +1 如: 34改为 134

        if (insertIndex +1 != i) {
            arr[insertIndex + 1] = insertVal;
        }
        System.out.println("第"+(i)+"轮插入后的结果为:");
        System.out.println(Arrays.toString(arr));
    }

最后一步我们来测试插入排序执行10w数据的执行时间,来看代码:

/**
 * 算法学习-插入排序
 */
public class InsertSort {
public static void main(String[] args) {

    //int [] arr = {101,34,119,1};
    //insertSort(arr);
    //插入的时间复杂度测试
    int [] arr = new int[100000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)(Math.random() * 100000); //随机生成[0,100000)的数
    }

    Date date1 = new Date();
    SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format = dateFormat.format(date1);
    System.out.println("排序前的时间为:"+format);
    //进行排序
    insertSort(arr);
    Date date2 = new Date();
    SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format2 = dateFormat.format(date2);
    System.out.println("排序后的时间为:"+format2);

}

来看测试结果图:

执行时间测试结果图.png

多次执行,发现10w数据插入排序算法只需要1s,当然可能跟计算机CPU有关系,我们发现插入排序执行的效率要高于选择排序和冒泡排序算法,那么关于插入排序的学习就到这里