阿里五面：说下希尔排序的过程？希尔排序的时间复杂度和空间复杂度又是多少？

1959年Shell发明，第一个突破 O(n^2^) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。

插入排序

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

代码实现：

function insertionSort(arr) {
    let n = arr.length;
    let preIndex, current;
    for (let i = 1; i < n; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

复杂度分析：

时间复杂度：O(n^2^)
空间复杂度：O(1)

希尔排序

回顾一下上面的插入排序：

第一趟插入排序后，我们得到的有效序列长度为 2
第二趟插入排序后，我们得到的有效序列长度为 3
...
直到这个序列有序

所以，如果序列足够乱的话，时间复杂度为 O(n^2^)

希尔排序又是如何优化的喃？

希尔排序又叫缩小增量排序，就是把数列进行分组(组内不停使用插入排序)，直至从宏观上看起来有序，最后插入排序起来就容易了(无须多次移位或交换)。

其中组的数量称为增量，显然的是，增量是不断递减的(直到增量为1)

那我们有是如何进行分组喃？

往往的： 如果一个数列有 8 个元素，我们第一趟的增量是 4 ，第二趟的增量是 2 ，第三趟的增量是 1 。如果一个数列有 18 个元素，我们第一趟的增量是 9 ，第二趟的增量是 4 ，第三趟的增量是2 ，第四趟的增量是 1

很明显我们可以用一个序列来表示增量：n/2、(n/2)/2、...、1，每次增量都/2

例如：

let arr = [4, 1, 5, 8, 7, 3]

排序前：

将该数组看成三组（ Math.floor(arr.length/2) )，分别是： [4, 8] ， [1, 7] ， [5, 3]

第一趟排序：

对三组数据分别进行插入排序，因此我们三个数组得到的结果为： [4, 8] ， [1, 7] ， [3, 5]

此时数组是这样子的：[4, 1, 3, 8, 7, 5]

第二趟排序：

增量减少了，上面增量是 3 ，此时增量应该为 1 了，因此把 [4, 1, 3, 8, 7, 5] 看成一个数组(从宏观上是有序的了)，对其进行插入排序，直至有序

代码实现：

function shellSort(arr) {
    let n = arr.length;
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < n; i++) {
            let j = i;
            let current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

复杂度分析：

时间复杂度：O(nlogn)
空间复杂度：O(1)

希尔排序是插入排序的修改版，是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

时间复杂度为 O(nlogn)，空间复杂度为O(1)

// shellSort
function shellSort(arr) {
  for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
    // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
    for(let i = gap; i < arr.length; i++) {
      let j = i;
      let temp = arr[j];
      for(; j> 0; j -= gap) {
        if(!(j - gap >= 0) || !(temp < arr[j - gap])) {
          break;
        }
        arr[j] = arr[j-gap];
      }
      arr[j] = temp;
    }
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
console.log(shellSort(arr));

@7777sea

@7777sea 代码有问题，运行结果：[0, 2, 5, 7, 9, 10, 10, 10, 11, 32, 90, undefined, -3: 1, -2: undefined, -1: undefined]

@elixiao

@elixiao 感谢指出，已经修改了～

分组那里有问题吧？应该是间隔多少增量为一组
增量直接用倍数也不好吧？
百度百科：

普林斯顿 ppt:
时间复杂度也不准确吧？
百度百科：

分组那里有问题吧？应该是间隔多少增量为一组

增量直接用倍数也不好吧？
百度百科：

普林斯顿 ppt:

时间复杂度也不准确吧？
百度百科：

这可以去查查论文吧根据不同的数组长度有不用的间隔数组选择吧有动态计算间隔的方法
var N=arr.length; var h=1; while(h<N/3){ h=3*h+1 } 其中h每次变化h=(h-1)/3

	let gap=[5,3,1];//原本就存在数组的情况
			function Shell(arr){
				var h;
				for(let g=0;g< gap.length;g++){
					 h=gap[g];
					for(let i=h;i<arr.length;i++){
						let temp=arr[i]
						let j=i;
						while(j > h-1 && arr[j-h]>temp){
							arr[j]=arr[j-h];
							j=j-h;
						}
						arr[j]=temp;
					}
				}
				return arr
			}
			
			//动态生成数组
			function sataticShell(arr){
				let h=1;
				let n=arr.length;
				while(h<n/3){
					h=3*h+1
				}
				
				while(h>=1){
					for(let i=h;i<arr.length;i++){
						let temp=arr[i];
						let j=i;
						while(j>=h && arr[j-h]>temp){
							arr[j]=arr[j-h]
							j-=h;
						}
						arr[j]=temp;
					}
					h=(h-1)/3
				}			
				return arr
				}

这个写的希尔排序为毛跟我看的不一样？难道不是间隔h？

@sisterAn

@sisterAn 第一趟增量是3，不是应该是[4,8],[1,7],[3,5]，第一趟结果[4,1,3,8,7,5]

@JerryWen1994

感谢 @JerryWen1994 已调整

Navigation Menu

Repository navigation

阿里五面：说下希尔排序的过程？希尔排序的时间复杂度和空间复杂度又是多少？ #75

插入排序

希尔排序

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

阿里五面：说下希尔排序的过程？ 希尔排序的时间复杂度和空间复杂度又是多少？ #75

Description

插入排序

希尔排序

Activity

7777sea commented on Jul 3, 2020

elixiao commented on Jul 6, 2020

7777sea commented on Jul 6, 2020

cutie6 commented on Jul 19, 2020

Verahuan commented on Jul 30, 2020

Verahuan commented on Jul 30, 2020

s15723 commented on Sep 1, 2020

JerryWen1994 commented on Jan 12, 2021

sisterAn commented on Apr 14, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

阿里五面：说下希尔排序的过程？希尔排序的时间复杂度和空间复杂度又是多少？ #75