排序算法-希尔排序

希尔排序

概念

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。

希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

过程

希尔排序就是按照一定的gap值，不断地对数组进行插入排序。不一样的希尔排序算法可能采用不一样的gap值。经典希尔算法的gap值为N/2, N/4, … 直到gap值为1，这里的N为数组的长度。

举个例子：
[8, 9, 1, 7, 2, 3, 5, 4, 6, 0] ,采取间隔 5 (gap = length/2)。创建一个位于 5 个位置间隔的所有值的虚拟子列表。下面这些值是 {8, 3}, {9, 5}, {1, 4}, {7, 6}, {2, 0}，我们这五个子序列分别进行插入排序。结果为 [3, 5, 1, 6, 0, 8, 9, 4, 7, 2] 。

接下来我们采取间隔 2（gap = 5/2），继续按位于2个间隔的所有值进行插入排序，这个间隔将产生以下两个子虚拟列表：[3, 1, 0, 9, 7] 与 [5, 6, 8, 4, 2]，都进行插入排序，结果为 [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]。

最后我们采取间隔 1 (gap = 2/2)，也就是对整个序列进行插入排序（此时的序列已经基本有序了），结果为 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。

实现

/**e
 * @description: 希尔排序
 * @param {Array} 
 */

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

shellSort([8, 9, 1, 7, 2, 3, 5, 4, 6, 0])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

希尔排序与直接插入排序区别

希尔排序是插入排序的优化：

1.当数组长度很大时，使用插入排序有个弊端，就是如果最小值排在很末端的时候，插入排序需要从末端开始，逐个往前比较到第一个位置，很低效。而希尔排序通过分组的方式，直接让前端跟末端的元素进行比较，解决了插入排序的这个弊端。

2.当一开始 增量n 很大的时候，每一个子数组的元素很少，所以对每个子数组用插入排序进行内部排序是很高效的；而后随着增量n不断减小，这个数组是越来越有序的，此时使用插入排序也是很有利的。