?个人博客：www.hellocode.top
?Java知识导航：Java-Navigate
?CSDN：HelloCode.
?知乎：HelloCode
?掘金：HelloCode
⚡如有问题，欢迎指正，一起学习~~
插入排序（Insertion Sort）是一种简单直观的排序算法，其基本思想是将一个记录插入到已排好序的有序序列中，直到所有记录插入完成为止。
基本思想
如上图所示，插入排序的基本思想就是将一个数组划分为两部分：有序部分和无序部分。通过将无序部分的元素依次插入有序部分（需要找到对应的正确位置），让每次插入的每个元素都能在正确的位置，保证有序部分始终有序，在将无序部分的元素全部插入到有序部分后，整个集合也就为有序的了。
- 从第二个元素开始，依次将当前元素插入到已排好序的有序序列中，直到最后一个元素。
- 插入当前元素时，从后往前遍历已排好序的有序序列，找到当前元素在有序序列中的位置，并将其插入到该位置。
- 重复执行步骤2，直到所有元素都插入完毕。
举个例子，比如我们有一组数字 [5, 3, 8, 4, 2]，我们可以首先把第一个数字5视为已排序序列，然后从第二个数字3开始，与已排序序列中的元素逐一比较，找到合适的位置插入。然后针对第三个数字8，我们再重复这个过程，直至所有的数字都插入到已排序序列中。
代码实现
具体的代码就是两层for循环，外层控制未排序部分的指针，内层不断循环寻找新插入元素的正确位置，代码如下：
下面展示Java和C两种版本（C语言版本由俺的女朋友小周提供?）
/**
* @author HelloCode
* @blog https://www.hellocode.top
* @date 2023年08月09日 21:45
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = {21, 64, 32, 11, 9, 5, 3, 41, 75, 32, 12, 98, 66};
System.out.println("排序前：" + Arrays.toString(arr));
insertSort(arr);
System.out.println("排序后：" + Arrays.toString(arr));
}
public static void insertSort(int[] arr) {
// 外层循环，i指向数组中未排序的元素，也可以表示已经有序元素的个数
for (int i = 1; i < arr.length; i++) {
// 内层for指向已经排好序的最后一个元素
for (int j = i - 1; j >= 0; j--) {
// 开始排序，寻找新加入的元素的正确位置，（j + 1）代表新加入的元素
if (arr[j + 1] >= arr[j]) {
// 代表不用交换，加入即有序，直接跳出循环
break;
}
// 否则需要进行交换，直到找到合适位置
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}测试：
//C语言实现：
void Insert_Sort(int* arr, int len)
{
assert(arr != NULL);
if (arr == NULL)
return;
int tmp；
int j; //将j的生存周期提高
for (int i = 1; i < len;i++) //每次从待排序队列中取的值（i=1;因为默认第一个值就是有序的）
{
tmp = arr[i]; //tmp保存待插入的值
for (j = i - 1; j >= 0; j--) //从右向左找不比tmp大的值
{
if (arr[j] > tmp) //如果比tmp大 则向右放一个
{
arr[j + 1] = arr[j];
}
else //如果不比tmp大 则退出进入arr[j+1]=tmp;
{
break; //触底的情况
}
}
arr[j + 1] = tmp; //将tmp保存到arr[j+1]中
}
}
void Show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 2,6,5,4,8,9,7,1,8,6 };
int len = sizeof(arr) / sizeof(arr[0]);
Insert_Sort(arr, len);
Show(arr, len);
return 0;
}//C++版本
#include <iostream>
#include <assert.h>
using namespace std;
void Insert_Sort(int* arr, int len)
{
assert(nullptr != arr);
if (nullptr == arr)
return;
int tmp, j;
for (int i = 1; i < len; i++) //每次从待排序队列中取的值（i=1;因为默认第一个值就是有序的）
{
tmp = arr[i]; //tmp保存待插入的值
for (j = i - 1; j >= 0; j--) //从右向左找不比tmp大的值
{
if (arr[j] > tmp) //如果比tmp大 则向右放一个
{
arr[j + 1] = arr[j];
}
else
{
break;
}
}
arr[j + 1] = tmp;
}
}
void Show(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int arr[] = { 2,6,5,4,8,9,7,1,8,6 };
int len = sizeof(arr) / sizeof(arr[0]);
Insert_Sort(arr, len);
Show(arr, len);
return 0;
}优化
对于插入排序，能够优化的点我认为是在为新插入元素寻找正确位置的时候，上面的代码采用的是依次比较，类似于冒泡排序的思想。如果数据量大且情况最差的时候，效率就有些不理想了，因此可以用其他方法在此处进行优化，提升插入排序的性能
二分查找：在每次需要插入元素时，使用二分查找来找到插入的位置，而不是从头到尾扫描已排序序列。这样可以将比较次数降低为O(log n)。
具体代码这里就不列了，后面可能会有专门的二分查找文章。
总结
优点
- 实现简单，对于部分有序的数组效率高。
- 对于小规模数据或者部分有序的数据，插入排序的运行时间相对较短。
缺点
- 对于大规模数据或者随机数据，插入排序的时间复杂度较高，为O(n^2)。
- 是非稳定的排序算法，即相等的元素可能会因为排序而变得顺序颠倒。
复杂度
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
使用场景
- 小型数据集：对于小型的数据集，插入排序是一种高效且简单的排序算法
- 部分排序的数据集：如果一个数据集大部分是排序的，那么插入排序将是一个很好的选择。例如，考虑一个场景，一个团队在一场比赛中获得了一组分数，这些分数按照高低已经被排序，但是有一个新的分数需要插入到合适的位置。在这种情况下，插入排序可以快速找到新分数的位置并把它插入到正确的位置。
- 外部排序：当处理非常大的数据集时，可能需要使用外部排序。外部排序是指那些不能一次性加载到内存中的数据的排序。在这种情况下，可以使用插入排序作为子程序，从外部存储器中读取元素并将它们插入到已经排序的部分中。
- 与其他算法结合：插入排序也可以与其他算法结合使用。例如，当需要先对数据进行排序，然后再进行一些复杂的操作时，可以使用插入排序作为预处理步骤。
1 条评论
打卡算法学习第三天！！！