PHP實現插入排序算法

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

';

　　?>

From:http://tw.wingwit.com/Article/program/PHP/201311/20783.html