数据结构和算法——贝壳排序
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 WHILE3、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。然后，我们执行标准的插入排序。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-11-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录