希尔排序本质是一种插入排序,由一位叫希尔的大神提出得名,其基本思想是将数组分组进行插入排序,每次消除不止一个逆序对,这样就提高了插入排序的效率。最后一步进行一间隔的插入排序,此时数组已经基本有序。代码实现如下:
function shellSort(arr){ if(!Array.isArray(arr)){ return false; //类型判断 } else{ var k = 1,len = arr.length,interval; while(Math.pow(2,k)<len){ k++; } interval = Math.pow(2,k-1)-1; //定义间隔 while(interval>0){ for (var i = interval; i < len; i++) { var cup = arr[i]; var j = i-interval; while(j>=0&&arr[j]>cup){ arr[j+interval] = arr[j]; j-=interval; } arr[j+interval] = cup; }; interval = (interval+1)/2-1; } return arr; } }
增量用了Hibbart增量,Dk=2^k-1; 据猜想其平均时间复杂度Tavg = O(N5/4); 希尔排序不是稳定排序,其排序效率与所用的增量序列有关。