PHP实现冒泡排序、双向冒泡排序算法

冒泡排序（Bubble Sort），是一种较简单的、稳定的排序算法。冒泡排序算法步骤：比较相邻的元素，如果第一个比第二个大，就交换他们两个的位置；对每对相邻的元素执行同样的操作，这样一趟下来，最后的元素就是最大的；除了已得出来的最大元素，把剩余的元素重复前面步骤，直到没有元素再需要比较为止，这样排序就完成了。冒泡算法，在最好情况下，时间复杂度为O(n)；在最坏情况下，时间复杂度为O(n²)；平均时间复杂度为O(n²)。

PHP实现冒泡排序、双向冒泡排序算法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149

<?php /** * 数据结构与算法（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>'; ?>