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

冒泡排序(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
　　$bubble = new BubbleSort(array(35, 75, 92, 41, 27, 58));
　　echo '
';
　　?>