冒泡排序（Bubble Sort），是一種較簡單的、穩定的排序算法。冒泡排序算法步驟：比較相鄰的元素，如果第一個比第二個大，就交換他們兩個的位置；對每對相鄰的元素執行同樣的操作，這樣一趟下來，最後的元素就是最大的；除了已得出來的最大元素，把剩余的元素重復前面步驟，直到沒有元素再需要比較為止，這樣排序就完成了。冒泡算法，在最好情況下，時間復雜度為O(n)；在最壞情況下，時間復雜度為O(n2)；平均時間復雜度為O(n2)。
PHP實現冒泡排序、雙向冒泡排序算法 1
/**
* 數據結構與算法（PHP實現） - 冒泡排序（Bubble Sort）。
*
* @author 創想編程（TOPPHP.ORG）
* @copyright Copyright (c) 2013 創想編程（TOPPHP.ORG） All Rights Reserved
* @license http://www.opensource.org/licenses/mit-license.php MIT LICENSE
* @version 1.0.0 - Build20130608
*/
class BubbleSort {
/**
* 冒泡排序。
*
* @var integer
*/
const SORT_NORMAL = 1;
/**
* 雙向冒泡排序。
*
* @var integer
*/
const SORT_DUPLEX = 2;
/**
* 需要排序的數據數組。
*
* @var array
*/
private $data;
/**
* 數據數組的長度。
*
* @var integer
*/
private $size;
/**
* 數據數組是否已排序。
*
* @var boolean
*/
private $done;
/**
* 構造方法 - 初始化數據。
*
* @param array $data 需要排序的數據數組。
*/
public function __construct(array $data) {
$this->data = $data;
$this->size = count($this->data);
$this->done = FALSE;
}
/**
* 交換數據數組中兩個元素的位置。
*
* @param integer $x 元素在數組中的索引。
* @param integer $y 元素在數組中的索引。
*/
private function swap($x, $y) {
$temp = $this->data[$x];
$this->data[$x] = $this->data[$y];
$this->data[$y] = $temp;
}
/**
* 冒泡排序。
*/
private function sort() {
$this->done = TRUE;
for ($i = 1; $i < $this->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) {
break ;
}
}
}
/**
* 雙向冒泡排序。
*/
private function duplexSort() {
$this->done = 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->size - 1; --$j, ++$k) {
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) {
break;
}
}
}
/**
* 獲取排序後的數據數組。
*
* @param integer $sort 排序算法：SORT_NORMAL為冒泡排序；SORT_DUPLEX為雙向冒泡排序。
* @return array 返回排序後的數據數組。
*/
public function getResult($sort = self::SORT_NORMAL) {
// 若已排序則無需再進行排序，直接返回排序好的數據數組。
if ($this->done) {
return $this->data;
}
switch ($sort) {
case self::SORT_DUPLEX:
$this->duplexSort();
break;
case self::SORT_NORMAL:
default:
$this->sort();
break;
}
return $this->data;
}
}
?>
示例代碼 1
2
3
4 <?php
$bubble = new BubbleSort(array(35, 75, 92, 41, 27, 58));
echo '<pre>', print_r($bubble->getResult(BubbleSort::SORT_DUPLEX), TRUE), '</pre>';
?>
