带你读《图解算法小抄》十四、排序（22）https://developer.aliyun.com/article/1348128?groupCode=tech_library
最后，我们使用间隔值为1对数组的剩余部分进行排序。希尔排序使用插入排序来对数组进行排序。
function shellSort(arr) { const len = arr.length; let gap = Math.floor(len / 2); while (gap > 0) { for (let i = gap; i < len; i++) { const current = arr[i]; let j = i; while (j >= gap && arr[j - gap] > current) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = current; } gap = Math.floor(gap / 2); } return arr; }
2）复杂度
名称 |
最佳情况 |
平均情况 |
最坏情况 |
内存 |
稳定性 |
备注 |
希尔排序 |
n log(n) |
取决于间隔序列 |
n (log(n))2 |
1 |
否 |
|
3）参考资料
- Tutorials Point
- 维基百科
- YouTube（Rob Edwards）
