研究了网上大部分的希尔排序代码,发现大部分都是互相抄的——因为网上甚至某些书上的实现大部分都是错的。希尔排序是插入排序的升级版,通过引入间隔,然后分组进行插入排序。再逐步缩小间隔,直至间隔为1时,做全数组的插入排序。dart 代码如下:

 1 void shellSort<E extends Comparable>(List<E> a) {  2   for (var i = _initInterval(a); i > 0; i = (i - 1) ~/ 3) {  3     for (var g = 0; g < i; g++) {  4       for (var j = i + g; j < a.length; j += i) {  5         var k = j - i, t = a[j];  6         while (k >= 0 && t.compareTo(a[k]) < 0) {  7           a[k + i] = a[k];  8           k -= i;  9  } 10         if (k < j - i) a[k + i] = t; 11  } 12  } 13  } 14 } 15 
16 int _initInterval<E>(List<E> a) { 17   var interval = 1; 18   while (interval < a.length ~/ 3) interval = interval * 3 + 1; 19   return interval; 20 }

 

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄