希尔排序
2024年04月03日
一、认识
希尔排序也称递减增量排序，是插入排序的一种改进版本，英文称为Shell Sort，效率虽高，但它是一种不稳定的排序算法。基本思路是先将整个数据序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全部数据进行依次直接插入排序。
特点:
- 不稳定排序: 如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
- 原地排序: 原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
- 排序方式: In-place (不占用额外内存，只占用常数内存)
- 时间复杂度:
O(n$log_{}{n}$)[n 代表数据规模及数据量大小] - 空间复杂度:
O(1)
扩展:
- 排序算法的稳定性:
假定在 待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
那么排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。
二、思想
- 将待排序数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组
- 逐渐缩小间隔进行下一轮排序
- 最后一轮时，取间隔为 11，也就相当于直接使用插入排序。但这时经过前面的「宏观调控」，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成
举例:
对数组 [84, 83, 88, 87, 61, 50, 70, 60, 80, 99][84,83,88,87,61,50,70,60,80,99] 进行希尔排序的过程如下：
- 第一遍（5 间隔排序）：按照间隔 5 分割子数组，共分成五组，分别是 [84, 50], [83, 70], [88, 60], [87, 80], [61, 99]。对它们进行插入排序，排序后它们分别变成： [50, 84], [70, 83], [60, 88], [80, 87], [61, 99]，此时整个数组变成 [50, 70, 60, 80, 61, 84, 83, 88, 87, 99]
- 第二遍（2 间隔排序）：按照间隔 2 分割子数组，共分成两组，分别是 [50, 60, 61, 83, 87], [70, 80, 84, 88, 99]。对他们进行插入排序，排序后它们分别变成： [50, 60, 61, 83, 87], [70, 80, 84, 88, 99]，此时整个数组变成 [50, 70, 60, 80, 61, 84, 83, 88, 87, 99]。这里有一个非常重要的性质：当我们完成 2 间隔排序后，这个数组仍然是保持 5 间隔有序的。也就是说，更小间隔的排序没有把上一步的结果变坏。
- 第三遍（1 间隔排序，等于直接插入排序）：按照间隔 1 分割子数组，分成一组，也就是整个数组。对其进行插入排序，经过前两遍排序，数组已经基本有序了，所以这一步只需经过少量交换即可完成排序。排序后数组变成 [50, 60, 61, 70, 80, 83, 84, 87, 88, 99]，整个排序完成。
三、实现
function sortArray(nums){
for(let gap=Math.floor(nums.length/2);gap>0;gap=Math.floor(gap/2)){
for(let i=gap;i<nums.length;i++){
let value=nums[i];
let index=i-gap;
while(index>=0&&value<nums[index]){
nums[index+gap]=nums[index];
index-=gap;
}
nums[index+gap]=value;
}
}
return nums;
}
性能分析:
- 时间复杂度: O(nlogn)
- 空间复杂度: O(1)