构想
将第一个待排序的序列看做一个有序序列,把第二个元素到最后一个元素当场是一个未排序
例如 : [ 5 ,11, 2 ,13 ,24,5];
第一个序列 :[5]
第二个至最后一个:[11,2, 13, 24 ,5 ]
扫描序列2 和序列一中的值依次比较
扫描第一次 序列1 是 [5, 11]
.
.
.
直到所有都扫描完成
动态演示
代码实现
javaScript 实现
function insertionSort(arr) {
var len = arr.length;
var preIndex , current;
for( var i = 1; i < len; i++) {
preIndex = i -1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current ){
arr[preIndex +1] = arr[preIndex];
preIndex --;
}
arr[preIndex + 1] = current;
}
return arr;
}
PHP 实现
function insertionSort($arr)
{
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
$preIndex = $i - 1;
$current = $arr[$i];
while($preIndex >= 0 && $arr[$preIndex] > $current) {
$arr[$preIndex+1] = $arr[$preIndex];
$preIndex--;
}
$arr[$preIndex+1] = $current;
}
return $arr;
}