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

在这里插入图片描述

👦个人主页：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;	}
}