给定如下所示的数字列表,请按升序对它们进行排序。
$numbers = [21,25,100,98,89,77];
要求
贝壳算法
。贝壳排序是插入排序的概括。与插入排序不同,它不比较连续项目,而是使用间隔i(称为间隔)将主列表分成几个子列表,然后使用插入排序对子列表进行排序。
我们重复上述步骤,直到间隙变为1,然后本质上应用标准的插入排序。
显然,空位序列在这种排序算法中起着重要作用。不幸的是,可以说没有完美的缺口序列。不同的研究人员得出了几个不同的空位序列,它们的性能在很大程度上取决于输入数据的大小。
以下是一些流行的空位序列:
FLOOR(N / 2k)
2p3q
(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
我们需要一个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。然后,我们执行标准的插入排序。