【排序算法】插入排序与希尔排序详解

10 0 0

排序算法专题：插入类排序解析
一、基础插入排序
 1.核心思想
 2.代码实现
 3.算法特性
 3.1时间效率分析
 3.2内存占用分析
 3.3排序稳定性
 二、进阶希尔排序
 1.设计思路
 1.1改进目标
 1.2优化策略
 2.实现方案
 2.1初始无序阶段
 2.2逐步有序阶段
 3.具体实现
 4.性能特征
 4.1时间效率
 4.2空间需求
 4.3稳定程度

数据交换机制
通过多变量暂存技术 可以达成 变量间的数值传递而不丢失原始信息，被释放的存储单元可重新承载新数据，而这些新数据又来自其他变量的转存， 这种机制支持 数据在存储单元间的迁移重组 ，是构建 排序算法 的重要基石
【排序算法】插入排序与希尔排序详解

一、基础插入排序

1.核心思想

该算法的核心在于将待排元素逐个插入到前方已排序序列的合适位置， 通过从首元素开始逐步构建有序序列，每次插入都确保新序列保持升序排列，直至所有元素完成插入操作 ，最终形成完整的有序数组
【排序算法】插入排序与希尔排序详解

2.代码实现

public static void insertionSort(int[] arr) {
for (int i = 1; i = 0 && arr[j] > current; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = current;
}
}

3.算法特性

3.1时间效率分析

首元素 自动构成初始有序序列无需比较 ， 后续每个元素都需要在前方有序序列中寻找合适的插入位置 ， 对于n个元素总共需要进行n-1轮插入操作：
* 当 输入数据已经有序 时，内层循环立即终止，时间复杂度为 线性O(n)
* 当 输入完全逆序 时， 每个元素都需要比较到有序序列的起始位置 ，比较次数呈等差数列增长，时间复杂度达到 平方级O(n²)

3.2内存占用分析

常数级空间复杂度O(1)

3.3排序稳定性

具有稳定性

二、进阶希尔排序

这是基础插入排序的高效改进版本

1.设计思路

1.1改进目标

基础版本中 固定的n-1轮插入操作无法改变 ，优化重点在于 尽可能减少每轮操作中的比较和移动次数

1.2优化策略

当 原始数据接近有序状态 时， 即元素初始位置与其最终排序位置较为接近 ，那么每轮插入时 所需比较和移动的次数就会显著减少：
_元素在插入时往往只需少量比较就能定位到正确位置，且该位置就是其在最终有序序列中的应有位置，表明 数据元素的初始分布与目标顺序高度吻合 ， _减少了排序过程中的调整需求__

2.实现方案

【排序算法】插入排序与希尔排序详解

2.1初始无序阶段

数据混乱时， 连续的插入操作会导致频繁的元素移动 ，因此：
采用 大跨度分组策略 ，使得 各组之间相对独立 ， 通过少量比较就能实现元素的远距离移动 ， 用较低成本实现数据的整体大致有序
【排序算法】插入排序与希尔排序详解

2.2逐步有序阶段

当数据达到基本有序后：
逐步缩小分组间隔至原值的一半 ， 随着数据有序度提升，采用更精细的分组策略 ， 充分利用现有有序性进行微调 ， 最终当间隔为1时，算法退化为标准插入排序，但此时数据已近乎完全有序

3.具体实现

public static void shellSort(int[] arr) {
int interval = arr.length;
while (interval > 1) {
interval >>= 1;
groupSort(arr, interval);
}
}
private static void groupSort(int[] arr, int step) {
for (int i = step; i = step && arr[j] > temp; j -= step) {
arr[j+step] = arr[j];
}
arr[j+step] = temp;
}
}