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

一.直接插入排序介绍🍗

直接插入排序又叫简单插入排序，是一种简单直观的排序算法，它通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述：

1. 假设要排序的列表为arr，列表的第一个元素arr[0]默认已经是有序序列。
2. 从第二个元素开始，即arr[1]，向前遍历已排序的部分，将该元素插入到正确的位置。
3. 在遍历已排序部分时，如果当前元素小于前一个元素，将当前元素与前一个元素交换位置，否则停止遍历。
4. 重复步骤2和步骤3，直到所有元素都被插入到正确的位置。

由于在每次插入过程中，需要不断比较和移动元素，最坏情况下时间复杂度为O(n^2)，其中n是要排序的元素个数。然而，若输入数据已经近乎有序，直接插入排序的效率会比较高，时间复杂度可接近O(n)。若完全有序，时间复杂度为O(n).

直接插入排序的特点：

不需要额外的空间

过程稳定

适用于数据规模较小且部分有序的情况

---

二.图解过程🍗

以下以数组6，3，4，5，7，1为例。从小到大排序

核心：取出无序部分的首个，在有序部分从后向前比较，插入到合适的位置

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)