數據結構和算法——貝殼排序

• 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。然後，我們執行標準的插入排序。