希尔排序
- 平均时间复杂度:O(nlogn)
- 最好情况:O(nlog^2n)
- 最坏情况:O(nlog^2n)
- 空间复杂度:O(1)
- 排序方式:In-place
- 稳定性:不稳定
算法步骤:
1.先取一个小于待排序数列长度n的整数d1作为第一个增量,将所有距离为d1的倍数的记录放在同一个组中。(一般的初次取序列的一半为增量,以后每次减半,直到增量为1。)
2.在各组内进行插入排序;
3.取第二个增量d2<d1重复上述的分组和排序,直至增量为1,即所有记录放在同一组中进行插入排序。
例如待排序数组为: [1, 10, 3, 2, 5, 8, 4, 7, 9, 6]
1.第一次增量设为数组长度的一半即5, 数组被分为五组分别为[1,8]/[10,4]/[3,7]/[2,9]/[5,6]
2.然后对每组做插入排序操作,操作后的数组为[1, 4, 3, 2, 5, 8, 10, 7, 9, 6]
3.第二次增量设为之前增量的一半取整即2,数组被分为两组分别为[1,3,5,10,9]/[4,2,8,7,6]
4.然后对每组做插入排序操作,操作后的数组为[1, 2, 3, 4, 5, 6, 9, 7, 10, 8]
5.第三次增量再次设为之前增量的一半即1,数组只分为一组,排序后结束。
function shellSort(arr) {
let len = arr.length;
let temp,
gap = len;
while ((gap >>= 1)) {
for (let i = gap; i < len; i++) {
temp = arr[i];
let j = i;
for (; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
改进
希尔排序的优化主要在增量的选择,上面的实现取了2,一般都是取2或3。 至于最优值是多少貌似仍是一个数学难题。
网友评论