【数据结构】插入排序详细图解（一看就懂）

前言引入

插入排序是一种非常有意思且比较高效的排序方法，同时插入排序是希尔排序的基础 。

我预备下一篇博客讲解希尔排序，这一篇就先讲一下插入排序。

在生活中，这种排序方法也随处可见。

例如，我们在玩扑克牌时，总会按照插入排序的方法调整扑克牌的位置。

玩扑克牌怎么会用到插入排序的方法呢？

当我们拿起第二张牌时，就会下意识的与第一张牌进行比较，如果比第一张牌小，我们就会将牌插入至第一张牌的左边，反之就插入至右边。

这样边插入边排序，就是插入排序，插入后的序列依旧是有序的。

大家先看一下下面的原理和代码，然后再看实例图可能会比较好。

插入排序的原理

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，我们就可以得到一个新的有序序列。

我们将原数组空间看成两个部分，前边是有序部分，后边是无序部分，有序部分我们默认为它就已经是排好序的，在尾部新加入的元素有可能会导致整个有序数组变得无序，因此我们需要进行调整。

调整方式就是将新加入的元素进行对比并往前移动，新加入元素和它前边的元素进行对比，如果它比它前边的元素小，则二者互换位置，不断重复这个过程，直到它前边的元素小于它才会停止，这样一来，他就仍然是有序数组。

插入排序源码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void InsertSort(int* a, int n)
{
  int tmp;
  int end;
  for (int i = 1; i < n; i++)
  {
  end = i - 1;
  tmp = a[i];
  while (end >= 0)
  {
    if (a[end] > tmp)
    {
    a[end + 1] = a[end];
    end--;
    }
    else
    {
    break;
    }
  }
  a[end + 1] = tmp;
  }
}
int main()
{
  int a[] = { 45,67,89,12,34,5,6,8,1,2,67,99,55 };
  InsertSort(a, sizeof(a) / sizeof(a[0]));
  for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
  {
  printf("%d ", a[i]);
  }
  return 0;
}
/*{ 45,45,89,12,34,5,6,8,1,2,67,99,55 };*/

运行结果

详细实例过程图解

下面用一组实例来解释。

就按这组数据为例，此时end处的值不大于i处的值，不用进入循环， a[end + 1] = tmp;不造成影响

第二次，同理，i++继续往后走。

第三次，这次不一样了！a[end]>a[i]，也就是a[end]大于tmp了，进入循环。

循环一次，完成 a[end + 1] = a[end];  end--;a[end+1]=tmp;的操作。

此时end值为1，大于0，循环继续。

循环两次，完成 a[end + 1] = a[end];  end--;a[end+1]=tmp;的操作。

此时end值为0，等于0，循环继续。

循环三次， 完成 a[end + 1] = a[end];  end--;a[end+1]=tmp;的操作。

此时end值为-1，小于0，循环结束。

第一次排序结束，下面的排序也就是比葫芦画瓢了，这里我就不列举了。

本章小结

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，是一种稳定的排序算法

4. 是否稳定：稳定