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

PHP

PHP实现插入排序算法

来源:中国IT实验室 作者:佚名 发表于:2013-07-01 10:22  点击:
插入排序(Insertion Sort),是一种较稳定、简单直观的排序算法。插入排序的工作原理,是通过构建有序序列,对于未排序的数据,在有序序列中从后向前扫描,找到合适的位置 并将其插入。插入排序,在最好情况下,时间复杂度为O(n);在最坏情况下,时间复杂度为O(
插入排序(Insertion Sort),是一种较稳定、简单直观的排序算法。插入排序的工作原理,是通过构建有序序列,对于未排序的数据,在有序序列中从后向前扫描,找到合适的位置 并将其插入。插入排序,在最好情况下,时间复杂度为O(n);在最坏情况下,时间复杂度为O(n2);平均时间复杂度为O(n2)。
  插入排序示例图:
\
  
  /**
  * 数据结构与算法(PHP实现) - 插入排序(Insertion Sort)。
  *
  * @author 创想编程(TOPPHP.ORG)
  * @copyright Copyright (c) 2013 创想编程(TOPPHP.ORG) All Rights Reserved
  * @license .opensource.org/licenses/mit-license.php MIT LICENSE
  * @version 1.0.0 - Build20130613
  */
  class InsertionSort {
  /**
  * 需要排序的数据数组。
  *
  * @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;
  }
  /**
  * 插入排序。
  */
  private function sort() {
  $this->done = TRUE;
  for ($i = 1; $i < $this->size; ++$i) {
  $current = $this->data[$i];
  if ($current < $this->data[$i - 1]) {
  for ($j = $i - 1; $j >= 0 && $this->data[$j] > $current; --$j) {
  $this->data[$j + 1] = $this->data[$j];
  }
  $this->data[$j + 1] = $current;
  }
  }
  }
  /**
  * 获取排序后的数据数组。
  *
  * @return array 返回排序后的数据数组。
  */
  public function getResult() {
  if ($this->done) {
  return $this->data;
  }
  $this->sort();
  return $this->data;
  }
  }
  ?>
  示例代码 1
  2
  3
  4
  $insertion = new InsertionSort(array(9, 1, 5, 3, 2, 8, 6));
  echo '
', print_r($insertion->getResult(), TRUE), '
';  ?>

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