PHP实战中知识总结 / 排序算法 - 希尔排序算法

一、希尔排序

希尔排序（Shell's Sort）是直接插入排序算法的一种更高效的改进版本，又称“缩小增量排序”（Diminishing Increment Sort）。

希尔排序是将要排序的数组按下标的一定增量进行分组，每组分别进行直接插入排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数组都被分成一组，算法结束。

二、步骤讲解

图示：

（1）初始数组：$arr = [3,9,2,5,7,6,8,1]

（2）初始增量：$gap = count($arr) / 2; // 4

数组被分成了四组：[3,7]，[9,6]，[2,8]，[5,1]。对每组分别进行排序后，结果为：[3,7]，[6,9]，[2,8]，[1,5]。因此结果集为：[3,6,2,1,7,9,8,5]。

（3）缩小增量：$gap = $gap / 2; // 2

数组被分为两组[3,2,7,8]，[6,1,9,5]，分别进行排序，结果为：[2,3,7,8]，[1,5,6,9]，结果集为：[2,1,3,5,7,6,8,9];

（4）增量大于1,需要继续缩小增量，重复第三步：$gap = $gap / 2; // 1

数组会被分为一组[2,1,3,5,7,6,8,9]，进行组内排序，由于增量已经等于1，算法结束，输出结果：[1,2,3,5,6,7,8,9]。

三、详细代码

$arr = [3,9,2,5,7,6,8,1];
$result = $this->shellSort($arr); // [1,2,3,5,6,7,8,9]
/**
* 希尔排序
* @param array $arr
* @return array|string
*/
function shellSort(array $arr)
{
  for ($gap = intval(count($arr) / 2); $gap > 0; $gap = intval($gap / 2)) { // 缩小增量
    for ($i = $gap; $i < count($arr); $i++) { // 组内循环排序
      $j = $i;
      while ($j - $gap >= 0 && $arr[$j] < $arr[$j - $gap]) { //完成组内元素一次排序
        $this->swap($arr, $j, $j - $gap);
        $j -= $gap;
      }
    }
  }
  return $arr;
}
/**
* 交换函数
* @param array $arr
* @param int $a
* @param int $b
*/
function swap(array &$arr, int $a, int $b)
{
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}