主页 > 知识库 > 网络编程 > PHP >

PHP

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

来源:中国IT实验室 作者:佚名 发表于:2013-07-02 11:15  点击:
冒泡排序(Bubble Sort),是一种较简单的、稳定的排序算法。冒泡排序算法步骤:比较相邻的元素,如果第一个比第二个大,就交换他 们两个的位置;对每对相邻的元素执行同样的操作,这样一趟下来,最后的元素就是最大的;除了已得出来的最大元素,把剩余的元素重复
冒泡排序(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 '
', print_r($bubble->getResult(BubbleSort::SORT_DUPLEX), TRUE), '
';
  ?>

    有帮助
    (0)
    0%
    没帮助
    (0)
    0%