PHP はバブル ソートと双方向バブル ソート アルゴリズムを実装します_PHP チュートリアル

バブルソートは比較的シンプルで安定したソートアルゴリズムです。バブルソートアルゴリズムのステップ: 隣接する要素を比較し、最初の要素が 2 番目の要素よりも大きい場合は、隣接する要素の各ペアに対して同じ操作を実行します。取得した最大の要素を削除し、比較する必要のある要素がなくなるまで残りの要素に対して前の手順を繰り返し、並べ替えが完了します。バブル アルゴリズムでは、最良の場合の時間計算量は O(n)、最悪の場合の時間計算量は O(n2)、平均の時間計算量は O(n2) です。

PHP はバブルソートと双方向バブルソートアルゴリズム 1 を実装します

/**
* データ構造とアルゴリズム (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 - Build20130608
​*/
クラスバブルソート {
/**
* バブルソート。
*
* @var 整数
​*/
const SORT_NORMAL = 1;

/**
* 双方向バブルソート。
*
* @var 整数
​*/
const SORT_DUPLEX = 2;

/**
* ソートする必要があるデータ配列。
*
* @var 配列
​*/
プライベート $data;

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

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

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

/**
* データ配列内の 2 つの要素の位置を交換します。
*
* @param integer $x 配列内の要素のインデックス。
* @param integer $y 配列内の要素のインデックス。
​*/
プライベート関数スワップ($x, $y) {
$temp = $this->data[$x];
$this->data[$x] = $this->data[$y];
$this->data[$y] = $temp; }

/**
* バブルソート。
​*/
プライベート関数 sort() {
$this->done = TRUE;

for ($i = 1; $i size; ++$i) {
//データ交換の回数を記録します。
$swap = 0;

for ($j = $this->size - 1; $j > $i - 1; --$j) {
If ($this->data[$j] < $this->data[$j - 1]) {
$this->swap($j - 1, $j);
++$swap;
}
}

// データ交換回数が 0 の場合は、データ配列が整っていてソートする必要がないことを意味します。
If (0 === $swap) {
休憩;
}
}
}

/**
* 双方向バブルソート。
​*/
プライベート関数 duplexSort() {
$this->完了 = TRUE;

for ($i = 1; $i <= Floor($this->size / 2); ++$i) {
//データ交換の回数を記録します。
$swap = 0;

for ($j = $this->size - 1, $k = $i - 1;
$j > $i - 1 && $k <$this-> サイズ - 1; If ($this->data[$j] < $this->data[$j - 1]) {
$this->swap($j - 1, $j);
++$swap;
}

If ($this->data[$k] > $this->data[$k + 1]) {
$this->swap($k, $k + 1);
++$swap;
}
}

// データ交換回数が 0 の場合は、データ配列が整っていてソートする必要がないことを意味します。
If (0 === $swap) {
休憩;
}
}
}

/**
* ソートされたデータ配列を取得します。
*
* @param integer $sort ソート アルゴリズム: SORT_NORMAL はバブル ソート、SORT_DUPLEX は双方向バブル ソートです。
* @return array ソートされたデータ配列を返します。
​*/
パブリック関数 getResult($sort = self::SORT_NORMAL) {
// ソートされている場合は、再度ソートする必要はなく、ソートされたデータ配列が直接返されます。
If ($this->done) {
$this->data;
を返す }

スイッチ ($sort) {
ケース self::SORT_DUPLEX:
$this->duplexSort();
休憩;

ケース self::SORT_NORMAL:
デフォルト:
$this->sort();
休憩;
}

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

サンプルコード1
2
3
4 $bubble = new BubbleSort(array(35, 75, 92, 41, 27, 58));
echo '

', print_r($bubble->getResult(BubbleSort::SORT_DUPLEX), TRUE), '

';
?>

http://www.bkjia.com/PHPjc/477265.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/477265.html技術記事バブル ソートは、比較的シンプルで安定したソート アルゴリズムです。バブルソートアルゴリズムの手順: 隣接する要素を比較し、最初の要素が 2 番目の要素よりも大きい場合は、両方を交換します...