柠檬铺

插入排序(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), '

';　　?>