转载声明：文章来源https://blog.csdn.net/weixin_56499830/article/details/124002124

1.直接插入排序原理
直接插入排序(Straight Insertion Sort)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

直接插入排序：将所有数据分为两个部分，一部分认为是有序的，一部分认为是无序的，每一次从无序部分取一个值放到我们有序部分，直到将无序部分全部取完。
从待排数组中依次取值，放到我们已经排序好的数组中

一个简单的例子：斗地主揭牌

我们从牌堆揭了一张A，现在要放到手牌中，一般来说都会插入到 2 与 J 之间
而直接插入排序就是这种思想


红线左边认为是有序的，红线右边是无序的
每一次从红线右边取一个值放到左边进行排序

第一次可以省略掉，直接从第二个数据开始处理
例如，在斗地主揭牌，第一张牌我们不需要看，揭第二张牌，我才需要看一下这张牌是多少，是向左放还是向右放。

第二次，取出22这个数据，与已经排好的数据比较，22大于11，所以不需要挪动，直接插入即可

第三次取出 7 这个数，与已经排好的数据比较，7 比 22 小，向左继续比较，7比11小，向左继续比较，此时触底，所以直接插入7.

第四次取出 5 这个数，与已经排好的数据比较，5 比 22 小，向左继续比较，5比11小，向左继续比较，5 比 7小，向左继续比较，此时触底，所以直接插入5.

第五次取出17这个数，与已经排好的数据比较，17 比 22 小，向左继续比较，17比11大，停止比较，插入17.

第六次的数据排好后，红线右边无数据，认为数组已经有序

用一句话描述调整过程：
将待插入的值 和 有序数组从右向左依次比较，找到小于等于自己的值
停下来，插入即可。
数据越有序，我们调用直接插入排序去比较挪动的次数越少，所以时间复杂度越低

2.代码实现

//直接插入排序  时间复杂度：O(n^2)    稳定性：稳定
//原始数据越有序   则调用直接插入排序的时间复杂度越低
void InsertSort(int *arr, int len)
{
	int count = 0;
	for(int i=1; i<len; i++)//控制的层数（次数）	//优化点  可以直接让i从1开始
	{
		int tmp = arr[i];
		int j;
		for(j=i-1; j>=0; j--)//从右向左找，不比tmp大的值，j控制和tmp比较的那个值的下标
		{
			if(arr[j] > tmp)//如果比tmp大  则向右挪动一格
			{
				count++;
				arr[j+1] = arr[j];
			}
			else//找到合适的插入位置 通过break退出
			{
				break;//优化点   这个else不参与赋值   只干一件事：找到插入数据的合适位置，赋值放到了for循环外边去处理
			}
		}
		arr[j+1] = tmp;//在外边给将tmp插入到合适的位置
	}
	printf("%d\n", count);
}