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

[sisterAn]

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)

[7777sea]

希尔排序是插入排序的修改版，是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至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));

[elixiao]

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

[7777sea]

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

[cutie6]

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

2. 增量直接用倍数也不好吧？
   百度百科：
   
   普林斯顿 ppt:
   

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

[Verahuan]

1. 分组那里有问题吧？应该是间隔多少增量为一组
   
2. 增量直接用倍数也不好吧？
   百度百科：
   
   普林斯顿 ppt:
   
3. 时间复杂度也不准确吧？
   百度百科：
   
   这可以去查查论文吧 根据不同的数组长度有不用的间隔数组选择吧 有动态计算间隔的方法
   var N=arr.length; var h=1; while(h<N/3){ h=3*h+1 } 其中h每次变化h=(h-1)/3

[Verahuan]

	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
				}

[s15723]

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

[JerryWen1994]

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

[sisterAn]

感谢 @JerryWen1994 已调整