通过对直接插入排序的分析，可知其时间复杂度为O（n2），但是，如果待排序序列为正序时，其时间复杂度可提高至O（n）。希尔排序正是对此进行改进的排序。希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻元素。通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。
下图演示了希尔排序中间隔序列是如何运行的：
下面我们通过js来实现希尔排序，代码如下：
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>JavaScript希尔排序</title> </head> <body> <script type="text/javascript"> function shellSort(nums){//希尔排序 var gaps=[5,3,1];//定义间隔区间 for(var g=0;g<gaps.length;g++){//一个一个间隔值开始 for(var i=gaps[g];i<nums.length;i++){//以间隔值遍历 var temp=nums[i];//选中元素 for(var j=i;j>=gaps[g]&&nums[j-gaps[g]]>temp;j-=gaps[g]){//如果前面一个大于后面一个 nums[j]=nums[j-gaps[g]];//后移 } nums[j]=temp;//填补 } } } function show(nums){//显示数组 for(var i=0;i<nums.length;i++){ document.write(nums[i]+' '); } document.write('<br>'); } var nums=[6,0,2,9,3,5,8,0,5,4]; show(nums);//6 0 2 9 3 5 8 0 5 4 shellSort(nums);//希尔排序 show(nums);//0 0 2 3 4 5 5 6 8 9 </script> </body> </html>
其排序过程如下：
希尔排序根据间隔序列的选取不同，时间复杂度也不同，但是需要注意，应该使间隔序列中的值没有除1以外的公因子，并且最后一个间隔值必须等于1。
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》