C语言--直接插入排序【排序算法|图文详解】

---

一.直接插入排序介绍🍗

1. 首先看第一个数字：6，把数组分为有序部分和无序部分。

2.把无序部分的第一个元素3，插入到有序部分的合适位置

?

3.重复2中的操作部分，直到所有元素都有序。

需要注意的是有时候需要多次比较，比如数字1，需要多次比较，一次插入。

?

?最后重复以上步骤，直至完全有序。

---

?三.代码分析🍗

• 由于第一个数字是有序的，因此n个数字只需要遍历n-1次，i的初始值设为1
• 由于每次插入时都是从前一个数字开始比较，我们可以设置j的初始值为i-1

• 完整代码

//直接插入排序(简单插入排序或者直接插入排序)
//第一个数字必然有序，所以从第二个数字开始的。
//从第二个数字开始, 从后往前找比当前数字小的, 找到后插入到这个小的数字的后面; 
//在找的过程中, 如果发现一个比当前数字大, 同时将这个数字往后挪.
#include <stdio.h>
void  InsertSort(int* arr, int len)//insert 插入
{
	int tmp;
	int j;
	for (int i = 1; i < len; i++)//i为当前需要处理的数字的下标,i从第二个数字下标1开始
	{
		tmp = arr[i];
		for (j = i - 1; j >= 0; j--)//从后往前找位置,同时移动数据
		{
			if (arr[j] > tmp)
			{
				arr[j + 1] = arr[j];
			}
			else
			{
				//arr[j + 1] = tmp;
				break;
			}
		}
		arr[j + 1] = tmp;
	}
}
void  Show(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d  ", arr[i]);
	}
	printf("\n");
}
int main()
{
	int arr[] = { 6,3,4,5,7,1};
	InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
	Show(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}

运行结果

---

四.效率分析🍗

时间复杂度：

最坏情况下：时间复杂度为O(n^2)

完全有序情况下：时间复杂度为O(n)

空间复杂度：O(1)