系列文章目录
目录
前言
欢迎来到我的新系列之——“排序算法”系类。
在这个系列里，我会介绍几种常见的且有用的排序算法，并详细介绍剖析它们的时间、空间复杂度等信息。目前已经确定的有：插入排序（直接插入和希尔排序）、选择排序（直接选择和堆排）、交换排序（冒泡和快排）、归并排序四类。随着学习的推进，未来博主还会分分享更多高效有用的排序算法。
那么这个系类的介绍就到这里，下面让我我们来进入第一篇排序算法学习：直接插入排序。
一、直接插入排序是什么？
在刚接触编程语言学习时，大家或多或少都接触过直接插入排序，所以我们对他其实并不陌生。
算法思想
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键值的大小，逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
举一个形象的例子：直接插入排序就像我们平常玩扑克牌，在拿到一张新牌后会将其插入到已经排好的牌中，这个过程其实就是将一个未排的数据插入已经排序好的数据集中。
二、直接插入排序为什么能做到排序
当插入第i个元素时，前面的a[0]、a[1]……a[i-1]已经排好序了，此时用新元素的排序码与排好的数据排序码集合做比较，在符合已有的排序顺序的前提下，找到合适的插入位置将a[i]插入，原位置上的数据右移。
这就是直接插入排序能做到排序的原因所在。
三、直接插入排序的实现
//直接插入排序
void InsertSort(int* a, int n)
{
if (!a)
{
perror("arr is NULL");
return;
}
//【0，end】为有序，temp即a[end+1]为插入数据；
//在一遍for循环结束后，【0，end+1】变有序；
//内循环while的作用是为a[end+1]寻找在【0，end+1】中合适的位置
for (int i = 0; i < n-1; ++i)
{
int end = i;
int temp = a[end + 1];
while(end>=0)
{
if (a[end] > temp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end+1] = temp;
}
}升序代码讲解：
①我们以int型数组为例。将数组首地址与数组数据个数传入函数；
②定义end变量，将end变量指向已经排好序集合的末尾。第一次进入循环时，没有排好的数据，此时默认end指向i=0，即第一个元素（单个元素肯定是有序的）；
③定义temp变量，指向将要插入数据的地址（数组下标）——即end之后第一位数据；
④进入循环，将a[end]依次与temp比较。这个循环的目的只有一个：将原有序数组中大于temp(即a[end+1]的数据后移)，为新数据特出空间；
⑤循环结束后，end+1的位置即使新数据应处的位置。
四、直接插入排序特性分析
1. 如果元素集合越接近有序，那么进入循环进行数据后移的次数就越少，直接插入排序算法的时间效率就越高；
2. 时间复杂度：考虑最坏的情况下，O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定。经过排序，这些记录的相对次序保持不变，即排前a[i]在a[j]前，排后依旧a[i]在a[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
总结
本文是【排序算法】系类第一篇，主要介绍了什么是直接插入排序，以及怎样实现插入排序，最后分析了直接插入排序的特性。
而接下来的希尔排序则是在直接插入排序上的优化，需要在理解了直接插入排序的基础上学习。
希望本文能对你有所帮助。
读完点赞，手留余香~