PHP實現插入排序算法

插入排序（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;
  }
}
?>

示例代碼 1
2
3
4 <?php
$insertion = new InsertionSort(array(9, 1, 5, 3, 2, 8, 6));
echo '<pre>', print_r($insertion->getResult(), TRUE), '</pre>';
?>