网站服务器转移视频吗,十堰秦楚网公众号,网站推广有哪些方式,房地产公司网站开发目录
前言
一、基本原理
1.算法步骤
2.动画演示
3.插入排序的实现代码
二、插入排序的时间复杂度
1. 时间复杂度
1.最优时间复杂度
2.最差时间复杂度
3.平均时间复杂度
2. 空间复杂度
三、插入排序的优缺点
1.优点
2.缺点
四、插入排序的改进与变种
五、插入排…
目录
前言
一、基本原理
1.算法步骤
2.动画演示
3.插入排序的实现代码
二、插入排序的时间复杂度
1. 时间复杂度
1.最优时间复杂度
2.最差时间复杂度
3.平均时间复杂度
2. 空间复杂度
三、插入排序的优缺点
1.优点
2.缺点
四、插入排序的改进与变种
五、插入排序的应用场景
六、总结 前言 插入排序Insertion Sort是一种简单且直观的排序算法常用于小规模数据的排序或作为其他复杂排序算法的一部分如快速排序的小数组优化。 本文将详细介绍插入排序的基本原理、实现代码、时间复杂度及其适用场景帮助你轻松掌握这一算法。
一、基本原理 插入排序的核心思想是将数组分为已排序部分和未排序部分。通过逐一从未排序部分取出元素将其插入到已排序部分的合适位置最终完成排序。
1.算法步骤 1. 从数组的第二个元素开始视为当前需要插入的元素。 2. 从已排序部分的最后一个元素开始比较如果当前元素较小则将已排序部分元素向右移动。 3. 重复上述步骤直到找到插入位置将当前元素插入。 4. 对剩余的未排序部分重复以上步骤直至整个数组有序。
2.动画演示 这里我写了一个程序用来演示直接插入算法的过程。 假如我要进行排序的数据元素分别为53, 862741。 初始的时候我们已排序中的部分中的数据元素使用绿色表示未排序的使用蓝色表示。 图1.初始状态 初始状态下我们把第一个数据元素看做一个已经排列好的部分。 同时把第二个数据元素作为下次要插入的数据元素。 图2.插入排序的动画演示 我们以上面的数组为例看一下具体的过程 53, 862741
1.第一轮 首先确定5是已经排列好的我们将3进行插入操作。将3插入到仅有一个数据元素为5的数组中显然5比3大我们将3插入到5的前面。至此第一轮插入结束。此时的数组为{3,5,8,6,2,7,4,1}。
2.第二轮 在上一轮中已排序的区间为{3,5},现在我们将8拿出来和前面排列好的部分进行比较。因为58,依次已排序区间应该为{3,5,8}。第二轮结束此时排序依然是{3,5,8,6,2,7,4,1}。
2.第二轮 在上一轮中已排序的区间为{3,5},现在我们将8拿出来和前面排列好的部分进行比较。因为58,依次已排序区间应该为{3,5,8}。第二轮结束此时排序依然是{3,5,8,6,2,7,4,1}。
3.第三轮 在上一轮中已排序的区间为{3,5,8},现在我们将6拿出来和前面排列好的部分进行比较。因为86,我们在把6和前面的一个数据元素5比较56把6查到5后面,依次已排序区间应该为{3,5,68}。第二轮结束此时排序依是{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. 作为复杂排序的辅助算法如快速排序或希尔排序中用插入排序优化小数组的排序效率。
六、总结 插入排序是一种经典的排序算法以其简单性和直观性被广泛应用于教学和小规模排序场景中。虽然它在大数据排序上的性能较差但通过改进如二分插入排序或结合其他算法如希尔排序可以显著提升效率。
