【数据结构】直接插入排序

在这里插入图片描述

👦个人主页：Weraphael
✍🏻作者简介：目前正在学习c++和算法
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章有啥瑕疵
希望大佬指点一二
如果文章对你有帮助的话
欢迎评论💬 点赞👍🏻 收藏 📂 加关注😍

一、基本思想

在这里插入图片描述

基本思想：把待排序的元素从小到（从大到小）逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中，玩扑克牌时，整理一副牌从小到大或者从大到小就用到了插入排序的思想

在这里插入图片描述

二、算法原理

首先序列中的第一个元素（下标为0）是不需要排序的。因为当插入第一个元素时，序列中也没有元素与其比较，因此默认为有序。
当插入第i（i ≥ 1）个元素时，由于要挪动数据，我们拿待插入元素与当前数组内的最后一个元素(下标end)进行比较，若a[i] < 数组最后一个元素，则将当前元素向后移动一个单位，并将end--继续向前比较，直到找到合适位置为止。

这里为大家举几个样例

插入1

在这里插入图片描述

插入3

在这里插入图片描述

插入5

在这里插入图片描述

三、代码实现

以下代码以升序为例：

#include <stdio.h>

// n - 元素个数
void InsertSort(int* a, int n)
{
	// 数组第一个元素不需要参与排序
	// 下标从1开始
	for (int i = 1; i < n; i++)
	{
		// end - 每一次数组最后一个元素的下标
		// InsertNum - 要插入的元素
		int end = i - 1; 
		int InsertNum = a[i];
		
		while (end >= 0)
		{
			// 如果插入的元素比当前元素小，就要往后挪动数据
			if (a[end] > InsertNum)
			{
				a[end + 1] = a[end];
				end--;
			}
			// 插入比当前元素大，则直接插入
			else
			{
				a[end + 1] = InsertNum;
				break;
			}
		}
		//当循环结束后，可能存在头插
		if (end == -1)
		{
			a[end + 1] = InsertNum;
	    }
	}
}

当然以上代码在插入过程中有重复代码，因此可以整合

#include <stdio.h>

// n - 元素个数
void InsertSort(int* a, int n)
{
	// 数组第一个元素不需要参与排序
	// 下标从1开始
	for (int i = 1; i < n; i++)
	{
		// end - 每一次数组最后一个元素的下标
		// InsertNum - 要插入的元素
		int end = i - 1; 
		int InsertNum = a[i];
		
		while (end >= 0)
		{
			// 如果插入的元素比当前元素小，就要往后挪动数据
			if (a[end] > InsertNum)
			{
				a[end + 1] = a[end];
				end--;
			}
			// 插入比当前元素大，则直接插入
			else
			{
				break;
			}
		}
		// 当循环结束后，存在两种情况
		// 1. 头插
		// 2. break跳出来的 
		// 以上情况直接插入即可
		a[end + 1] = InsertNum;	
	}
}