Shell Sort

[barretlee]

6 提到了三种最基本的排序算法，这里要提到的希尔排序，有点不好理解。

/chapters/chapter-2-sorting/2.1-elementary-sorts/shell.js

function shell(input) {
  var h = 1;
  var len = input.length;
  while(h < Math.floor(len / 3)) {
    h = h * 3 + 1;
  }
  while(h >= 1) {
    for(var i = h; i < len; i++)  {
      for(var j = i; j >= h; j -= h) {
        if(input[j] < input[j - h]) {
          input[j] = [input[j - h], input[j - h] = input[j]][0];
        }
      }
    }
    h = Math.floor(h / 3);
  }
  return input;
}

算法复杂不代表需要很多的代码去实现，因为代码表达的是过程，通过循环等方式可以很迅速实现一个过程，而算法是处理问题的方法，把它表达清楚可能就得费不少唇舌，甚至还得配上一些图辅助阅读。

希尔排序，大概的思路就是不断地从整体上调整数据的顺序，将比较大的数据尽量往后挪，比较小的数据尽量往前挪。数据的搬移也不是一步完成，每一次搬移都会将数据分块，分块的目的是尽可能的搬移距离比较远的数据，从而减少比较操作和交换操作。