PHP implements insertion sort algorithm_PHP tutorial

Insertion Sort is a relatively stable, simple and intuitive sorting algorithm. The working principle of insertion sort is to construct an ordered sequence. For unsorted data, scan from back to front in the ordered sequence to find the appropriate position and insert it. Insertion sort, in the best case, the time complexity is O(n); in the worst case, the time complexity is O(n2); the average time complexity is O(n2).

Insertion sort example diagram:

/**
* Data structure and algorithm (PHP implementation) - Insertion Sort.
*
* @author Chuangxiang Programming (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 {
/**
* The data array that needs to be sorted.
*
* @var array
​*/
private $data;

/**
* The length of the data array.
*
* @var integer
​*/
private $size;

/**
* Whether the data array is sorted.
*
* @var boolean
​*/
private $done;

/**
*Construction method - initialize data.
*
* @param array $data The data array to be sorted.
​*/
public function __construct(array $data) {
$this->data = $data;
$this->size = count($this->data);
$this->done = FALSE;
}

/**
* Insertion sort.
​*/
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;
}
}
}

/**
* Get the sorted data array.
*
* @return array Returns the sorted data array.
​*/
public function getResult() {
If ($this->done) {
Return $this->data;
}

$this->sort();

Return $this->data;
}
}
?>

Sample code 1
2
3
4 $insertion = new InsertionSort(array(9, 1, 5, 3, 2, 8, 6));
echo '

', print_r($insertion->getResult(), TRUE), '

';
?>

http://www.bkjia.com/PHPjc/477271.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/477271.htmlTechArticleInsertion Sort is a relatively stable, simple and intuitive sorting algorithm. The working principle of insertion sort is to construct an ordered sequence. For unsorted data, in order...