当前位置：首页 > article >正文

排序算法 —— 直接插入排序

article 2024/10/21 4:02:22

1.直接插入排序的思想

2.直接插入排序的实现

实现分析

实现代码

3.直接插入排序的分析

时间复杂度分析

空间复杂度分析

稳定性

1.直接插入排序的思想

直接插入排序的思想就是把待排序的元素按其关键码值的大小依次插入到一个已经排好序的有序序列中，直到所有的元素插入完为止，得到一个新的有序序列。

在我们日常生活中，玩扑克牌时，其实就是运用了直接插入排序的思想。

2.直接插入排序的实现

实现分析

当只有一个元素的时候，这一个元素肯定是有序的，所以，从第二个元素开始，直到后面的所有元素都是待排序的元素。

因此，我们只需要从左到右依次枚举待排序的元素，将待排序的元素插入到有序序列中即可。

比如：当我们要排升序的时候，枚举到4的时候，4就是待排序元素，4大于它的前一个元素，说明4所在位置值正确的，不需要做其他操作。当我们枚举到2的时候，2就是待排序的元素，对于这种情况，下面的图中，很详细的讲解了这种情况下如何实现一个元素的插入逻辑。

需要注意的是：

枚举待排序元素的时候是从左到右枚举，并且是从第二个元素开始枚举，直到最后一个元素。（因为第一个元素本来就是有序的）
寻找插入位置是从右往左开始寻找的，最后插入的时候，是赋值给end+1的位置。（因为，我们每次都去和end位置的值作比较，当end位置的值小于tmp中保存的值的时候，end+1就是要插入的值）

实现代码

#include <stdio.h>

void InsertSort(int* nums, int n)
{
	// [0,end]有序，把end+1位置的插入到前序序列
	// 控制[0,end+1]有序
	int i = 0;
	for (i = 1; i < n; i++)      // 枚举待排序的元素 
	{
		int tmp = nums[i];       // 保存待排序的值
		
		// 依次和前一个位置比较，寻找插入位置 
		int end = i-1;
		while (end >= 0)         
		{
			if (tmp < nums[end]) // 当tmp小于end位置的值的时候，需要继续寻找插入位置 
			{
				nums[end + 1] = nums[end];
				--end;
			}
			else                 // 当tmp大于or等于end位置的值的时候，说明找到了插入位置 
			{
				break;
			}
		}
		
		// 将tmp中保存的值插入到正确的位置 
		nums[end + 1] = tmp;
	}
}

int main()
{
	int nums[] = { 3,4,2,1,7,8,5,6 };
	InsertSort(nums, 8);
	
	int i = 0;
	while(i < sizeof(nums)/sizeof(int))
	{
		printf("%d ",nums[i]);
		i++;
	}
	

	return 0;
}

代码运行结果如下：