前言

      回顾一下上一篇讲了一个什么内容？讲述了时间复杂度和额外空间复杂度，在时间复杂度中，描述了如何比较算法流程哪个更快，又介绍了选择排序。如果想要看第一章的话，请点击：算法：通过简单的排序算法来认识时间复杂度 进行观看。

      下面，小编我要进行介绍另一个排序：插入排序。插入排序是小编不太清楚的，没有冒泡排序和选择排序熟悉，通过今日的学习，进行了解和深入，希望这篇博客可以将我所学到的精髓展示出来。

一、插入排序的介绍（用例子）

      插入排序没有冒泡排序和选择排序那么傻，他还是需要一些技巧的。下面请看图：还是利用英雄从哪里来的图形：（英雄从哪里来大佬写的算法）。

   插入排序基本上是在0到j上进行比较，将j位置上的数与比j位置小的数进行一一比较，如果比他小/大，则进行交换数字，由上面的图形可以清楚的看到。下面进行代码实现：

for (int i = 0; i < n - 1; i++) //做到有序
{
  for (int j = i ; j >= 0 && arr[j + 1] < arr[j]; j--)  //j+1位置的数永远是要处理的数
  {
        //这种交换方式在后面进行讲解
        //arr[j] = arr[j] ^ arr[j + 1];
    //arr[j + 1] = arr[j] ^ arr[j + 1];
    //arr[j] = arr[j] ^ arr[j + 1];
        //交换变量
    int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
  }
}

二、为什么插入排序和冒泡(选择)排序不一样

      选择排序和冒泡排序的时间复杂度和数据状况完全是无关的，是一个严格的流程，数据状况不管是什么样，都需要进行操作。

      举个例子：选择排序，第一步在0到N-1上，不管是什么数据状况都需要进行一遍，然后进行第二步，然后......不管数据状况是好是坏，时间复杂度是没有发生变化的。冒泡排序也如此，在0到N之间，进行两个数之间的比较，与数据状况无关。

       而插入排序的时间复杂度和数据状况是有关。

      举个例子：用一个情况最糟的数据：7 6 5 4 3 2 1，用插入排序的时间复杂度为O(N^2)，如果用一个有序的数据：1 2 3 4 5 6 7，只用将前一个数与后一个数进行比较，不用交换，用插入排序的时间复杂度为O(N)。

      由第一章内容可知，插入排序的时间复杂度为O(N^2)，虽然时间复杂度与其他两个排序的时间复杂度是一样的，但是插入排序在常数级别的操作比那两个排序更优，因为不是每次数据都是情况最糟的。

总结

      以上就是今天要讲的内容，本文介绍了插入排序和其时间复杂度，希望大家看完以后，进行点评，谢谢大家！