日照网站建设多少钱产品的网络推广要点
目录
前言
一、基本原理
1.算法步骤
2.动画演示
3.插入排序的实现代码
二、插入排序的时间复杂度
1. 时间复杂度
1.最优时间复杂度
2.最差时间复杂度
3.平均时间复杂度
2. 空间复杂度
三、插入排序的优缺点
1.优点
2.缺点
四、插入排序的改进与变种
五、插入排序的应用场景
六、总结
前言
插入排序（Insertion Sort）是一种简单且直观的排序算法，常用于小规模数据的排序或作为其他复杂排序算法的一部分（如快速排序的小数组优化）。
本文将详细介绍插入排序的基本原理、实现代码、时间复杂度及其适用场景，帮助你轻松掌握这一算法。
一、基本原理
插入排序的核心思想是将数组分为已排序部分和未排序部分。通过逐一从未排序部分取出元素，将其插入到已排序部分的合适位置，最终完成排序。
1.算法步骤
1. 从数组的第二个元素开始，视为当前需要插入的元素。
2. 从已排序部分的最后一个元素开始比较，如果当前元素较小，则将已排序部分元素向右移动。
3. 重复上述步骤，直到找到插入位置，将当前元素插入。
4. 对剩余的未排序部分重复以上步骤，直至整个数组有序。
2.动画演示
这里我写了一个程序用来演示直接插入算法的过程。
假如我要进行排序的数据元素分别为5，3，, 8，6，2，7，4，1。
初始的时候，我们已排序中的部分中的数据元素使用绿色表示，未排序的使用蓝色表示。
图1.初始状态
初始状态下，我们把第一个数据元素看做一个已经排列好的部分。
同时把第二个数据元素作为下次要插入的数据元素。
图2.插入排序的动画演示
我们以上面的数组为例看一下具体的过程：
5，3, 8，6，2，7，4，1
1.第一轮
首先确定5是已经排列好的，我们将3进行插入操作。将3插入到仅有一个数据元素为5的数组中，显然5比3大，我们将3插入到5的前面。至此第一轮插入结束。此时的数组为{3,5,8,6,2,7,4,1}。
2.第二轮
在上一轮中，已排序的区间为{3,5},现在我们将8拿出来和前面排列好的部分进行比较。因为5<8,依次已排序区间应该为{3,5,8}。第二轮结束，此时排序依然是{3,5,8,6,2,7,4,1}。
2.第二轮
在上一轮中，已排序的区间为{3,5},现在我们将8拿出来和前面排列好的部分进行比较。因为5<8,依次已排序区间应该为{3,5,8}。第二轮结束，此时排序依然是{3,5,8,6,2,7,4,1}。
3.第三轮
在上一轮中，已排序的区间为{3,5,8},现在我们将6拿出来和前面排列好的部分进行比较。因为8>6,我们在把6和前面的一个数据元素5比较，5<6，把6查到5后面,依次已排序区间应该为{3,5,6，8}。第二轮结束，此时排序依是{3,5,6,8,2,7,4,1}。
4.第四轮
在上一轮中，已排序的区间为{3,5,6,8},现在我们将2拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同，这里不重复了，此时排序是{2,3,5,6,8,7,4,1}。
5.第五轮
在上一轮中，已排序的区间为{2,3,5,6,8},现在我们将7拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同，这里不重复了，此时排序是{2,3,5,6,7,8,4,1}。
3.第六轮
在上一轮中，已排序的区间为{2,3,5,6,7,8},现在我们将4拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同，这里不重复了，此时排序是{2,3,4,5,6,7,8,1}。
3.第三轮
在上一轮中，已排序的区间为{2,3,4,5,6,7,8},现在我们将1拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同，这里不重复了，此时排序是{1,2,3,4,5,6,7,8}
3.插入排序的实现代码
以下是插入排序的 C语言实现：
#include <stdio.h>
// 插入排序函数
void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i]; // 当前要插入的元素int j = i - 1;// 将比 key 大的元素向右移动while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 插入 key 到正确的位置arr[j + 1] = key;// 打印当前排序步骤printf("第 %d 步: ", i);for (int k = 0; k < n; k++) {printf("%d ", arr[k]);}printf("\n");}
}
int main(int argc, const char * argv[]) {int arr[] = {5, 3, 8, 6, 2, 7, 4, 1};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");// 执行插入排序insertionSort(arr, n);// 打印排序后的数组printf("排序后数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}二、插入排序的时间复杂度
1. 时间复杂度
1.最优时间复杂度
当数组已经有序时，每次插入只需比较一次，无需移动元素。
2.最差时间复杂度
当数组为逆序时，每次插入都需要将所有已排序部分元素向右移动。
3.平均时间复杂度
一般情况下，插入排序的性能表现介于最佳和最差之间。
2. 空间复杂度
插入排序是原地排序算法，只需常数级别的额外空间，空间复杂度为O(1) 。
三、插入排序的优缺点
1.优点
1. 简单直观：算法易于理解和实现。
2. 适合小数据集：对于小规模数据排序性能较好。
3. 稳定性：插入排序是稳定排序算法，不会改变相同元素的相对位置。
4. 局部有序优化：当数据部分有序时，插入排序的性能非常接近线性时间。
2.缺点
1. 效率低下：对于大规模数据，插入排序的性能较差，时间复杂度较高。
2. 多次元素移动：在数组为逆序的情况下，插入排序需要频繁移动元素，效率较低。
四、插入排序的改进与变种
1. 二分插入排序
• 改进点：在插入时，通过二分查找定位插入位置，从而减少比较次数。
• 时间复杂度：虽然查找位置优化为 ，但元素移动次数仍为 。
2. 希尔排序（Shell Sort）
• 基于插入排序的改进版，通过引入增量分组的思想，对远距离元素进行预排序，逐步缩小分组间隔，最终变为插入排序。
• 时间复杂度：最优可达 。
五、插入排序的应用场景
1. 小规模数据排序：在数据量较小时，插入排序简单易用，且性能尚可。
2. 近乎有序数据：插入排序在处理已部分有序的数据时表现优异。
3. 作为复杂排序的辅助算法：如快速排序或希尔排序中，用插入排序优化小数组的排序效率。
六、总结
插入排序是一种经典的排序算法，以其简单性和直观性被广泛应用于教学和小规模排序场景中。虽然它在大数据排序上的性能较差，但通过改进（如二分插入排序）或结合其他算法（如希尔排序），可以显著提升效率。