算法系列01----插入排序
2022/7/27 14:25:18
本文主要是介绍算法系列01----插入排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
插入排序法
1.工作原理(算法思路)
新建一个指针,指针左边的所有元素都是有序的。但是他们的位置并不是最终位置,一个指针从左向右扫描,若指针所在处的元素比左边元素小,则将该元素向前浮动至适当位置,使指针左侧元素仍然保持有序。当指针扫描到整个数组元素的末尾时,数组排序完成。
2.动图演示
3.C#代码实现
根据原理设计算法:
class Program { //插入排序法 public static void insertSort(int[] array) { //for循环:i作为指针,进行从左到右扫描数据的工作 //指针i从1开始扫描,因为i=0时指针左侧无元素 for (int i = 1; i < array.Length; i++) { //temp作为指针键值 int temp = array[i]; //新建变量j,从i开始向左扫描已经有序的元素,并与temp比较 //若temp小于扫描元素,则将j指针元素向右移位腾出空间 int j = i; while (j > 0 && array[j - 1] > temp) { array[j] = array[j - 1]; j--; } //循环完成后将temp放在j指针位置,完成本次插入 array[j] = temp; } } //打印数组 public static void printArray(int[] array) { foreach (int item in array) { Console.Write(item + "\t"); } Console.WriteLine(); } //主函数入口 static void Main(string[] args) { int[] array = new int[10] { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; printArray(array); insertSort(array); printArray(array); Console.ReadKey(); } }折叠
输出结果:
4.性能分析
1)复杂度
2)插入排序法特点
- 在数组元素规模较小的时候,插入排序法的运行效率很高。其经常用在一些其他排序方法中(比如归并排序以及快速排序)来对排序进行优化。
- 不同于选择排序法,当一个数组几乎有序的时候,插入排序法所需要的时间要比其他的排序法快得多。因此插入排序法的排序时间取决于数组元素的初始顺序,在最好的情况下,插入排序法运行时间能达到线性级别。
这篇关于算法系列01----插入排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?