PHP が挿入ソート アルゴリズムを実装する_PHP チュートリアル

挿入ソートは、比較的安定した、シンプルで直感的なソート アルゴリズムです。挿入ソートの動作原理は、順序付けされたシーケンスを構築し、順序付けされたシーケンス内で後ろから前に向かってスキャンして、適切な位置を見つけて挿入することです。挿入ソートの場合、時間計算量は最良の場合は O(n)、最悪の場合は時間計算量は O(n2)、平均時間計算量は O(n2) になります。

挿入ソートの図例:

/**
* データ構造とアルゴリズム (PHP 実装) - 挿入ソート。
*
* @author Chuangxiang Programming (TOPPHP.ORG)
* @copyright Copyright (c) 2013 TOPPHP.ORG All Rights Reserved
* @license http://www.opensource.org/licenses/mit-license.php MIT ライセンス
* @バージョン 1.0.0 - Build20130613
​*/
クラス InsertionSort {
/**
* ソートする必要があるデータ配列。
*
* @var 配列
​*/
プライベート $data;

/**
* データ配列の長さ。
*
* @var 整数
​*/
プライベート $size;

/**
* データ配列がソートされているかどうか。
*
* @var boolean
​*/
プライベート$完了;

/**
※構築方法 - データを初期化します。
*
* @param array $data ソートするデータ配列。
​*/
パブリック関数 __construct(array $data) {
$this->data = $data;
$this->size = count($this->data);
$this->done = FALSE;
}

/**
* 挿入ソート。
​*/
プライベート関数 sort() {
$this->完了 = TRUE;

for ($i = 1; $i <$this->size; ++$i) {
$current = $this->data[$i];

If ($current < $this->data[$i - 1]) {
for ($j = $i - 1; $j >= 0 && $this->data[$j] > $current; --$j) {
$this->data[$j + 1] = $this->data[$j];
}

$this->data[$j + 1] = $current;
}
}
}

/**
* ソートされたデータ配列を取得します。
*
* @return array ソートされたデータ配列を返します。
​*/
パブリック関数 getResult() {
If ($this->done) {
$this->data;
を返す }

$this->sort();

$this->data;
を返す }
}
?>

サンプルコード1
2
3
4 $insertion = new InsertionSort(array(9, 1, 5, 3, 2, 8, 6));
echo '

'、print_r($insertion->getResult(), TRUE)、'