网站后台演示地址,上海专业做网站,学院网站建设项目的活动分解,广州网站建设 企业核心思想
插入排序是一种基于元素比较的原地排序算法#xff0c;其核心思想是将数组分为“已排序”和“未排序”两部分#xff0c;逐个将未排序元素插入到已排序部分的正确位置。
例如扑克牌在理牌的时候#xff0c;一般会将大小王、2、A、花牌等按大小顺序插入到左边其核心思想是将数组分为“已排序”和“未排序”两部分逐个将未排序元素插入到已排序部分的正确位置。
例如扑克牌在理牌的时候一般会将大小王、2、A、花牌等按大小顺序插入到左边3、4等小牌会往右边靠这和插入排序是同一个原理 复杂度
时间复杂度
场景时间复杂度具体说明最佳情况O(n)数组已完全有序每次只需比较一次无需移动元素最差情况O(n²)数组完全逆序每个元素需比较并移动所有已排序元素如 [5,4,3,2,1]平均情况O(n²)部分有序数组的插入操作需要约 n²/4 次比较和移动
空间复杂度
O(1)原地排序算法仅需固定数量的额外空间如 key 和索引变量 j
代码实现Java
//插入排序升序排序举例
void insertionSort(int[] arr) {int n arr.length;for (int i 1; i n; i) {int key arr[i];int j i - 1;//不断向左移动直到找到自己的位置while (j 0 arr[j] key) {arr[j 1] arr[j];j j - 1;}arr[j 1] key;}
}
