插入排序(Insertion Sort)是一种较稳定简单直观的排序算法插入排序的工作原理是通过构建有序序列对于未排序的数据在有序序列中从后向前扫描找到合适的位置并将其插入插入排序在最好情况下时间复杂度为O(n);在最坏情况下时间复杂度为O(n);平均时间复杂度为O(n)
插入排序示例图
/**
* 数据结构与算法(PHP实现) - 插入排序(Insertion Sort)。tw.WingWit.CoM
*
* @author 创想编程(TOPPHP.ORG)
* @copyright Copyright (c) 2013 创想编程(TOPPHP.ORG) All Rights Reserved
* @license /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), '
';
?>
