希尔排序又被称为缩小增量排序，是对直接插入排序的优化改进，核心思路是先让数组元素按一定的间隔分组，对每组分别进行插入排序，随着排序进行逐步缩小间隔，直到间隔为1时完成最后一次插入排序，整个数组就变成有序状态。
希尔排序的核心逻辑
希尔排序的关键在于间隔序列的选择，不同的间隔序列会影响排序的效率。常见的初始间隔选择是数组长度的一半，之后每次将间隔减半，直到间隔为1。每次按间隔分组后，每组内的元素会进行插入排序，这样经过多轮分组排序后，数组的有序程度会越来越高，最后一轮间隔为1的插入排序就会非常高效。
JavaScript实现希尔排序的步骤
实现过程可以分为以下几步：
- 初始化间隔gap，通常初始值为数组长度的一半
- 当gap大于0时，循环执行分组排序操作
- 对每个间隔下的分组，分别进行插入排序
- 每轮排序完成后，将gap减半，进入下一轮
- 直到gap为1完成最后一次排序，返回有序数组
完整JavaScript代码示例
下面是一个基于动态间隔序列的希尔排序实现，间隔每次减半直到为1：
function shellSort(arr) {
// 复制原数组，避免修改原数组
const result = [...arr];
let gap = Math.floor(result.length / 2);
// 间隔大于0时持续排序
while (gap > 0) {
// 对每个间隔下的分组进行插入排序
for (let i = gap; i < result.length; i++) {
const temp = result[i];
let j = i;
// 组内插入排序，比较同组元素
while (j >= gap && result[j - gap] > temp) {
result[j] = result[j - gap];
j -= gap;
}
result[j] = temp;
}
// 缩小间隔
gap = Math.floor(gap / 2);
}
return result;
}
// 测试示例
const testArr = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0];
console.log('原数组:', testArr);
console.log('排序后数组:', shellSort(testArr));代码逻辑说明
上面的代码中，首先复制了输入的数组，防止直接修改原数组。初始间隔设为数组长度的一半，然后进入循环，每次循环中对所有间隔为gap的元素进行插入排序。在组内插入排序时，从当前组的第二个元素开始，和同组的前一个元素比较，如果前一个元素更大就交换位置，直到找到合适的位置插入当前元素。每轮排序完成后将gap减半，直到gap为0时结束循环，返回排序后的数组。
希尔排序的特性分析
希尔排序的时间复杂度依赖于间隔序列的选择，目前还没有绝对最优的间隔序列，常见的减半间隔序列的平均时间复杂度约为O(n^1.3)到O(n^2)之间，空间复杂度为O(1)，属于原地排序算法。它是不稳定的排序算法，因为分组排序过程中相同元素可能会被分到不同组，导致相对顺序改变。适合处理中等规模的数据排序，相比直接插入排序在数据量较大时效率提升明显。
希尔排序JavaScript排序算法间隔序列修改时间：2026-06-03 01:10:45