基本思想
- 希尔排序是一种基于插入排序的排序算法，也叫「缩小增量排序」，先看看插入排序的优缺点：
- 插入排序的优点：对于几乎有序的数组（每个元素距离它排好序以后的位置都不会太远）而言，时间复杂度可以达到线性 O(N)；
- 插入排序的缺点：如果一个较小的数在数组靠后的位置，那么它要来到前面要消耗很长时间。
- 希尔排序会将数组逐渐整理成「几乎有序」的样子（以便利用插入排序的优点），最后再执行一次「插入排序」，以完成排序任务；
- 希尔使用的是缩小增量（或者称有间隔的）的插入排序方法，以增量为步长划分子序列，即属于同一子序列的元素，下标的步长等于增量；
- 对每一个子序列应用插入排序，不断缩小增量，当增量为 1 的时候所有的数组元素都在一个子序列中，执行一次插入排序，数组最终有序；
示例图解
-
希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序，整个数组就有序了；
-
在此则选择增量
gap = length/2，缩小增量以gap = gap/2的方式，用序列{n/2, (n/2)/2，...，1 }来表示； -
希尔排序克服了插入排序的缺点，一个较小的数可以很快来到数组靠前的部分。间隔的选择是从大到小直至为 1；
- 间隔越大，每一次执行插入排序的元素越少；
- 反之，间隔越小，每一次执行插入排序的元素越多；
-
在最开始的时候参与插入排序的元素个数是较少的，利用了插入排序的优点，之后的每一轮，虽然间隔减少，但是数组越来越有序，插入排序可以较快完成；
![]( "希尔排序")
复杂度
-
时间复杂度：
O(n^(1.3-2)) -
空间复杂度：
O(1)
代码实现
由于 希尔排序 是基于插入排序的，插入排序的插入操作有两种；
- 逐个交换到前面合适的位置；
- 先暂存当前变量，然后将前面的若干个元素逐个向后赋值；
所以 希尔排序 的实现也有两种；
-
逐个交换到前面合适的位置
const shellSort = (nums) => { let len = nums.length; // 初始增量为 len/2 向下取整，每一次之后 len/2 向下取整 for (let gap = len >> 1; gap > 0; gap >>= 1) { // 对每一趟通过 gap 分割出来的子序列，进行插入排序，逐渐形成接近排序的数组 nums // 将 nums[i] 插入到区间 [0, i) 使之成为有序数组 for (let i = gap; i < len; i++) { // 从后向前逐个交换，直到前面的那个元素小于或者等于当前要插入的这个元素 for (let j = i; j > 0; j -= gap) { if (nums[j - gap] > nums[j]) { [nums[j - gap], nums[j]] = [nums[j], nums[j - gap]]; // 交换位置 } else { break; // 插入后无需再比较，跳出循环 } } } } return nums; } -
先暂存当前变量，然后将前面的若干个元素逐个向后赋值
const shellSort = (nums) => { let len = nums.length; // 初始增量为 len/2 向下取整，每一次之后 len/2 向下取整 for (let gap = len >> 1; gap > 0; gap >>= 1) { // 对每一趟通过 gap 分割出来的子序列，进行插入排序，逐渐形成接近排序的数组 nums for (let i = gap; i < len; i++) { let temp = nums[i]; // 暂存这个元素 let preIndex = i; // 大于 temp 的所有元素逐个后移 while (preIndex >= gap && nums[preIndex - gap] > temp) { nums[preIndex] = nums[preIndex - gap]; preIndex -= gap; } // 将 temp 处的值插入到合适的位置处 nums[preIndex] = temp; } } return nums; }
打赏作者
您的打赏是我前进的动力
微信
支付宝
比较排序🔮 插入排序
上一篇
评论
