购物车功能网站怎么做的,网站建设模板公司,龙岗网站建设联系电话,海南app网站建设目录
1、插入排序
2、流程介绍
3、java实现
4、性能介绍 前言 在 Java 中#xff0c; 冒泡排序#xff08;Bubble Sort#xff09; 和 选择排序#xff08;Selection Sort#xff09; 之后#xff0c;下一个性能更好的排序算法通常是 插入排序#xff08;Insertion …目录
1、插入排序
2、流程介绍
3、java实现
4、性能介绍 前言 在 Java 中 冒泡排序Bubble Sort 和 选择排序Selection Sort 之后下一个性能更好的排序算法通常是 插入排序Insertion Sort。 虽然它们的时间复杂度都是 O(n²)但在实际应用中插入排序通常比选择排序和冒泡排序更快尤其是在处理部分有序数据时表现更优。
总结Java 排序算法进阶路线 O(n²) 算法适合学习原理 冒泡排序最慢→ 选择排序 → 插入排序推荐先学 O(n log n) 算法实际应用 归并排序稳定→ 快速排序最快但不稳定→ 堆排序空间省 Java 内置排序 Arrays.sort()对基本类型用 快速排序对象类型用 归并排序保证稳定性。 1、插入排序 Insertion Sort插入排序是一种简单直观的排序算法适合小规模数据或部分有序数据。 1、核心思想 将数组分为 已排序 和 未排序 两部分逐个将未排序部分的元素插入到已排序部分的正确位置。 2、适合场景 小规模数据或基本有序的数据如日志按时间插入。 3、时间复杂度 最坏情况下为O(N*N)此时待排序列为逆序或者说接近逆序。 最好情况下为O(N)此时待排序列为升序或者说接近升序。 4、空间复杂度O(1)。 2、流程介绍
如下图所示 步骤
1.从第一个元素开始该元素可以认为已经被排序. 2.取下一个元素tem从已排序的元素序列从后往前扫描. 3.如果该元素大于tem则将该元素移到下一位. 4.重复步骤3直到找到已排序元素中小于等于tem的元素. 5.tem插入到该元素的后面如果已排序所有元素都大于tem则将tem插入到下标为0的位置. 6.重复步骤2~5. 3、java实现
代码示例如下
public class InsertionSort {/*** 插入排序升序* param arr 待排序数组*/public static void insertionSort(int[] arr) {if (arr null || arr.length 1) {return; // 边界条件数组为空或长度≤1时无需排序}// 从第二个元素开始下标1默认第一个元素已排序for (int i 1; i arr.length; i) {int current arr[i]; // 当前待插入的元素int j i - 1; // 已排序部分的最后一个元素下标// 从后往前遍历已排序部分寻找插入位置while (j 0 arr[j] current) {arr[j 1] arr[j]; // 比 current 大的元素向后移动j--;}// 插入 current 到正确位置arr[j 1] current;}}public static void main(String[] args) {int[] arr {12, 11, 13, 5, 6};System.out.println(排序前: Arrays.toString(arr));insertionSort(arr);System.out.println(排序后: Arrays.toString(arr));}
}
输出
排序前: [12, 11, 13, 5, 6]
排序后: [5, 6, 11, 12, 13]
关键步骤解析 外层循环 从 i 1 开始默认 arr[0] 是已排序部分。 每次迭代处理一个未排序元素 current arr[i]。 内层循环 从 j i - 1 开始反向遍历已排序部分。 如果 arr[j] current则将 arr[j] 向后移动一位。 直到找到 arr[j] ≤ current 的位置此时 j 1 就是 current 的插入位置。 插入操作 将 current 放入 arr[j 1]。 4、性能介绍 ✅ 为什么插入排序比选择排序快 比较次数更少选择排序每一轮都要遍历剩余全部元素找最小值而插入排序在数据基本有序时只需少量比较。 提前终止如果数据已经有序插入排序内层循环会立即终止类似冒泡优化版。 数据局部性插入排序是顺序访问数组对 CPU 缓存更友好。 总结 小数组排序 Java 的 Arrays.sort() 在子数组长度 ≤ 47 时会切换到插入排序。 部分有序数据 如日志按时间插入、游戏排行榜实时更新。 混合排序算法 快速排序的递归基改用插入排序如 QuickSort InsertionSort。 参考文章
1、六大排序算法插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序-CSDN博客https://blog.csdn.net/weixin_50886514/article/details/119045154?ops_request_misc%257B%2522request%255Fid%2522%253A%25220faf03d22b2d125d5f49a4649ad59c85%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257Drequest_id0faf03d22b2d125d5f49a4649ad59c85biz_id0utm_mediumdistribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119045154-null-null.142^v102^controlutm_term%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8Fspm1018.2226.3001.4187
