Python 官方文档:入门教程 => 点击学习
目录一、算法介绍二、算法思想三、算法原理四、动图演示五、代码实现六、算法分析6.1 时间复杂度6.2 空间复杂度一、算法介绍 插入排序,也称为直接插入排序。插入排序是简单排序中效率最
插入排序,也称为直接插入排序。插入排序是简单排序中效率最好的一种,它也是学习其他高级排序的基础,比如希尔排序/快速排序,所以非常重要,而它相对于选择排序的优点就在于比较次数几乎是少了一半。
每次将待排序的元素插入到已排序的序列中,直至全部插入完成。
核心代码
public class InsertionSort {
// 插入排序
public static void sort(Comparable[] a){
for (int i = 1;i < a.length;i++){
for (int j = i;j > 0;j--){
//比较索引j处的值与索引j-1处的值,如果j-1索引处的值大,则交换数据,反之,则找到了合适的位置,退出循环
if (greater(a[j - 1],a[j])){
swap(a,j - 1,j);
}else{
break;
}
}
}
}
//比较 v 是否大于 w
public static boolean greater(Comparable v,Comparable w){
return v.compareTo(w) > 0;
}
//数组元素交换位置
private static void swap(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
方法调用
public class InsertionSortTest {
public static void main(String[] args) {
Integer[] arr = {3,44,38,5,47,15,36,26,27};
InsertionSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
//排序前:{3,44,38,5,47,15,36,26,27}
//排序后:{3,5,15,26,27,36,38,44,47}
当待排序的 n 个元素是正序排列时,是排序的最佳情况,只需要比较(n-1)次,时间复杂度是O(n);最坏的情况是该序列是反序排列,此时就需要比较n(n-1)/2次,时间复杂度为 O(n²)。
插入排序的平均时间复杂度为 O(n²)
插入排序的空间复杂度为常数阶O(1)
到此这篇关于图解Java经典算法插入排序的原理与实现的文章就介绍到这了,更多相关Java插入排序内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: 图解Java经典算法插入排序的原理与实现
本文链接: https://www.lsjlt.com/news/167295.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0