PHP实现插入排序算法

发布时间：2015-05-27 19:26:16作者：知识屋

插入排序（Insertion Sort），是一种较稳定、简单直观的排序算法。插入排序的工作原理，是通过构建有序序列，对于未排序的数据，在有序序列中从后向前扫描，找到合适的位置并将其插入。插入排序，在最好情况下，时间复杂度为O(n)；在最坏情况下，时间复杂度为O(n2)；平均时间复杂度为O(n2)。

插入排序示例图：

<?php
/**
* 数据结构与算法（PHP实现） - 插入排序（Insertion 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 - 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;
}
}
?>