直接插入排序：

插入排序整体来看还是一个挺简单的排序  可以这么比喻 有一群士兵 每个人都有属于自己的编号 但编号是随机的 现在要求他们迅速地按照编号排成一排 那每个士兵都要根据自己的编号去找属于自己的位置  插入排序的思想 跟这个类似

如上图 我们一开始的数据是有序的 现在插入个数 我们要保证插入数据后我们的这4个数据也是有序的 我们实现的步骤：

① 把插入的数据有一个变量存储(这里我用tmp)

② 从插入数据的前一个数据依次遍历 与tmp比较 如果比tmp大则该数据往后移一位 如果比tmp小 则tmp填入它的前面

如果说给我们一个数组 我们只需把第一个数据看成有序 第二个数据是插入的数据 把他们排成有序 根据这样的思路以此类推 得出这样的代码：

void InsertSort(int* a, int n)//插入排序
{
  for (int i = 1; i < n; i++)
  {
    int end = i;
    int tmp = a[end];
    while (end > 0)
    {
      if (tmp < a[end - 1])
      {
        a[end] = a[end - 1];
        end--;
      }
      else
      {
                a[end] = tmp;
        break;
      }
    }
  }
}

 我这里是把插入数据的位置作为起始的遍历的位置 把它与前一个数进行比较 当然也可以把插入数据的前一个数据作为比较的起始位置 只不过最后填入数据的时候是 a[end+1]=tmp 具体的边界判断大家下去可以试试

回归我们之前的问题 大家看了上面的代码 觉得这样对嘛？ 

其实有一个边界的问题不知道大家是否注意到了没有

就是假设现在有两个数据 第二个数据为插入的数据 此时我们的end指向第二个数据(end=1) 我们与第一个数据比较 假设比较的结果是 第二个数据 要和 第一个数据 交换那么交换后end指向第一个数据 的位置(end=0) 此时我们想把tmp放进去 可是 此时还能进入while的循环嘛？  是不是就不能了 可是我们的tmp还没放进去呢 这样不就出问题了吗？

 也许你会想 “那我们把while(end>0)改成while(end>=0)不就行了嘛” 真的这样就可以纠正问题了嘛？

如果改成那样  现在我们继续刚刚的操作 我们此时 end=0 进去了 比较的时候我们与 end-1 位置的数据比较 0-1=-1 这样是不是越界了呢？所以这样是不可行的

咋们正确的做法应该是在while循环的外面进行tmp的填入：

void InsertSort(int* a, int n)//插入排序
{
  for (int i = 1; i < n; i++)
  {
    int end = i;
    int tmp = a[end];
    while (end > 0)
    {
      if (tmp < a[end - 1])
      {
        a[end] = a[end - 1];
        end--;
      }
      else
      {
        break;
      }
    }
    a[end] = tmp;
  }
}

大家这样看 我们此时无论是end=0跳出来 还是比较时跳出来 都会执行tmp的填入 这样不就解决了嘛 大家看是不是这个道理？

直接插入排序的时间复杂度：

现在大家看完插入排序的代码实现 大家算一算这个插入排序的时间复杂度时多少呢？

 首先 我们的最坏的时间复杂度时O(n^2) ：这种情况就是我们每次进行插入数据的操作 每次插入数据的前面的每个数据都会往后移动 也就是 9 8 7 6 5 4 3 2 1 排成升序

其次 我们最好的时间复杂度是O(n) 也就是 给我们的数据本身就是有序的 也就只会遍历一遍数据就没了

虽然我们最坏的时间复杂度是O(n^2) 但是这并不代表我们的插入排序就不好了 毕竟一个完全没有顺序的数组还是少见 这样看来内 我们的时间复杂也就没那么大了

我们的直接插入排序整体来讲还是挺好的

稳定性：稳定

冒泡排序：

相信对于这个排序大家应该也不陌生  我们就是 依次遍历 两两比较 每次遍历结束 至少有一个数会被放到它该有的位置 ：

void swap(int* p, int* q)
{
  int tmp = *p;
  *p = *q;
  *q = tmp;
}
void BubbleSort(int* a, int n)//我这里的n是总的数组大小
{
  for (int i = 0; i < n - 1; i++)
  {
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (a[j] > a[j + 1])
      {
        swap(a + j, a + j + 1);
      }
    }
  }
}

冒泡排序的时间复杂度：

这样写出的代码大家来看一下我们的时间复杂度是多少呢？

很显然 我们最坏的时间复杂度：O(n^2)  稳定性：稳定

我们最好的时间复杂度：O(n^2) (因为哪怕我们现在给的数组是有序的 我们还是会全部遍历完才结束)  

那我们是不是可以改进下呢 让它不必每次都要去遍历？

void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
        int flag=0;
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (a[j] > a[j + 1])
      {
                flag=1;
        swap(a + j, a + j + 1);
      }
    }
        if(!flag) break;
  }
}

 大家看这样是不是就解决了呢 我们第一遍遍历 如果没有发生交换 那么flag依旧等于0 下一次遍历之前判断 flag是否等于0 如果等于说明 数组已经有序不必再继续遍历了

那现在我们的插入排序 和冒泡排序(改过后)的时间复杂度是差不多的 那到底哪一个会更好一点内？ 

大家觉得上面的数组 用插入排序 和 冒泡排序 哪一个会更好呢？

我们比较 他们数之间的比较次数就可以了  大家数一下是多少呢？

插入排序：8次 冒泡排序：7+6次 是不是这样呢

所以我们这样来看的话 还是我们的直接插入排序会更好一点！

总的来讲：如果顺序有序的话 那插入和冒泡是一样的  但如果是局部有序的话或者说是接近有序 那么插入排序的适应性就更好 比较次数也更少