1. 概述

思路：取一个按规律缩小的间隔直至间隔缩小到1，每取一次间隔要对所有的数进行一次插入排序，以此来达到排序目的。和希尔排序相比，间隔大的是否排序少，间隔小的时候排序数在附近。

稳定性：不稳定（因为在每次间隔排序的时候，原序一样大小的数字可能分到不同组，不同组在排序时就改变了同大小数字的位置）

2. 实现代码

```php <?php class ShellSort { private $ori = []; public $new = []; public function __construct(array $arr) {

  $this->ori = $arr;
  $r = $this->shell($this->ori);
  $this->new = $r;

}

private function shell(array $arr) {

  // 确定间隔（Knuth序列，有其他序列：质数序列）
  $h = 1;
  while ($h <= count($arr) / 3) {
      $h = $h * 3 + 1;
  }
  // 循环步长
  for ($gap = $h; $gap > 0; $gap = ($gap - 1) / 3) {
      echo $gap."\t";
      // 需要与前面数据对比的元素
      for ($i = $gap; $i < count($arr); $i++) {
          // 按照间隔对比并交换数据
          for ($j = $i; $j > $gap - 1; $j -= $gap) {
              if ($arr[$j] < $arr[$j - $gap]) {
                  $arr = self::swap($arr, $j, $j - $gap);
              }
          }
      }
  }
  return $arr;

}

public static function swap(array $arr, int $i, int $j) {

  $tmp = $arr[$i];
  $arr[$i] = $arr[$j];
  $arr[$j] = $tmp;
  return $arr;

} }

$arr = [9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2]; $cls = new ShellSort($arr); print_r($cls->new); ```

希尔排序

1. 概述

2. 实现代码