数据结构和算法——贝壳排序

• 2019 年 11 月 29 日
• 筆記

1、要解决的问题

给定如下所示的数字列表，请按升序对它们进行排序。

$numbers = [21,25,100,98,89,77];

要求

• 对数字进行排序时，需要使用插入贝壳算法。
• 用PHP实现该算法

2、伪代码说明

贝壳排序是插入排序的概括。与插入排序不同，它不比较连续项目，而是使用间隔i（称为间隔）将主列表分成几个子列表，然后使用插入排序对子列表进行排序。

我们重复上述步骤，直到间隙变为1，然后本质上应用标准的插入排序。

显然，空位序列在这种排序算法中起着重要作用。不幸的是，可以说没有完美的缺口序列。不同的研究人员得出了几个不同的空位序列，它们的性能在很大程度上取决于输入数据的大小。

以下是一些流行的空位序列：

• 贝壳顺序：FLOOR（N / 2k）
• 普拉特序列：2p3q
• Knuth顺序：（3k – 1）/ 2

在本篇中，我们将使用贝壳顺序。

描述贝壳排序的伪代码如下：

Caculate gap size ($gap)        WHILE $gap is greater than 0            FOR each element of the list, that is $gap apart                Extract the current item                Locate the position to insert                Insert the item to the position            END FOR            Calculate gap size ($gap)        END WHILE

3、PHP实现贝壳排序

我们需要一个FOR循环和一个WHILE循环。我们使用FOR循环来迭代主列表，并使用WHILE循环来定位插入项目的位置。

<?php  $numbers = [21, 25, 100, 98, 89, 77];    $gap  = floor(count($numbers)/2);    while ($gap > 0) {        for ($i = 0; $i < count($numbers) - $gap; $i++) {            $extractItem = $numbers[$i + $gap];            $positionFound = $i + $gap;            while (($positionFound - $gap) > 0 && $extractItem < $numbers[$positionFound - $gap]) {                $numbers[$positionFound] = $numbers[$positionFound - $gap];                $positionFound = $positionFound - $gap;          }            $numbers[$positionFound] = $extractItem;      }        $gap = floor($gap/2);  }    print_r($numbers);    // Output:  /*  Array  (      [0] => 21      [1] => 25      [2] => 77      [3] => 89      [4] => 98      [5] => 100  )  */

该实现与插入排序类似，不同之处在于，我们比较的是间隔为$ gap的项，直到$ gap的值变为1。然后，我们执行标准的插入排序。