转载

插入排序以及优化

插入排序是一种非常重要的排序算法，对于接近有序的数组来说，使用插入排序进行排序可能要比使用归并排序等O(NlogN)级别的排序算法还要快，很多高级的算法也都采用了插入排序的思想。这里总结一下，插入排序的思想以及插入排序的优化方式。

记得我一开始学习插入的排序的时候，总是习惯这么写插入排序(用PHP来实现，用其他语言也是一样):

<?php
$rand_arr = [6,5,1,7,3];
$array_count = count($rand_arr);
for($i=1;$i<$array_count;$i++){
    //每次取出数组中的第i个元素与数组中的index小于i的元素进行比较
    //如果需要比较的数据大于第i个元素，就进行数据的交换，将较大值放到第i的位置
    //从第0个元素开始向左进行运动，内部循环一次取出前i个元素中的某一个元素与第i个元素进行比较
    for($j=0;$j<$i;$j++){
        if($rand_arr[$j] > $rand_arr[$i]){
            $temp = $rand_arr[$j];
            $rand_arr[$j] = $rand_arr[$j+1];
            $rand_arr[$j+1] = $temp;
        }
    }
}
print_r($rand_arr);
?>

排序的顺序如下:

开始阶段: [ 6 5 1 7 3 ] : i =1,指向index=1的元素，也就是5,j=0,指向index=0的元素，也就是6

开始第一次外部循环: 6和5进行比较，因为5<6,所以进行数据交换的操作(6和5进行交换)，得到一下的结果 [ 5 , 6 , 1 , 7 , 3 ],此时j+1 = 1, j=i,所以内部循环结束，开始第二轮外部循环。

开始第二轮外部循环: i=2,指向index=2的元素，也就是1，j=0,指向index=0的元素，也就是5。因为1小于5，所以进行交换，得到以下的结果[ 1 , 6 , 5 , 7 , 3 ],i就等于5。此时j+=1,j=1,继续进行内部循环，因为5小于6,所以继续进行交换，依次内推。整个循环过程如下:

[ 6 5 1 7 3 ]

[ 5 6 1 7 3 ]

[ 1 6 5 7 3 ]

[ 1 5 6 7 3 ]

[ 1 3 6 7 5 ]

[ 1 3 5 7 6 ]

[ 1 3 5 6 7 ]

经过上面的分析，大家可以看出，当第i个元素要与第0个元素到第i-1个元素进行比较的时候，第0个元素到第i-1个元素总是保持有序的(这一点，非常的总要，这也是插入排序的重要特点之一)。好了，既然是有序的，当我取出第i个元素进行比较的时候，如果第i个元素，小于第j个元素，那就意味者第i个元素要小于第j个元素到第i-1个元素了，后面的内部循环的比较就可以不进行比较了，这样我们就可以节省下进行数据不比较的比较的资源的消耗了。改写的代码如下:

<?
$rand_arr = [ 随机数组 ];
$array_count = count($rand_arr);
for($i=1;$i<$array_count;$i++){
    //改为从右到左进行比较排序
    for($j=$i-1;$j>=0;$j--){
        if($rand_arr[$j]>$rand_arr[$j+1]){
            //进行数据的交换
            $temp = $rand_arr[$j];
            $rand_arr[$j] = $rand_arr[$j+1];
            $rand_arr[$j+1] = $temp;
        }else{ //提前退出内层循环可以减少数据的比较
            break;
        }
    }
}
?>

好了，上面的优化方案，会帮助我们减少不比较的数据比较，但是插入排序中数据的交换次数还是很多，一次数据交换，相当于三次赋值操作，如果我们能够降低数据的交换操作，用别的方式来实现数据的交换，就肯定能提高插入的排序的执行效率。下面我直接贴出代码，大家先看一下:

<?php
$rand_arr = [随机数组];
$array_count = count($rand_arr);
for($i=1;$i<$array_count;$i++){
    $compare_value = $rand_arr[$i];
    for($j=$i;$j>0;$j--){
        if($compare_value < $rand_arr[$j-1]){
            $rand_arr[$j] = $rand_arr[$j-1];
        }else{
            $rand_arr[$j] = $compare_value;
            break;
        }
    }
    if($j==0){
        $rand_arr[0]=$compare_value;
    }
}
?>

我说一下，上面代码的思路:加入需要的排序的数组还是上面的 [ 6 5 1 7 3 ]。在初始的状态下，i = j =1,都指向5，这时候取出第i个元素5,将该值赋予给比较变量compare_value，以这个变量为基准与第j-1的元素到第o个元素进行比较(从右到左)，如果compare_value的值小于第j-1个元素，就将第j个原始设置为第j-1个元素的值。如果compare_value的值大于或者第j-1个元素，就将第j个元素设置为compare_value的值，根据插入排序的第0个元素到第j-1的元素的有序性，下面就不需要进行比较了。排序的过程如下:

初始状态下:[ 6 5 1 7 3 ] — i=j=1,都指向元素5，取出第i个元素作为比较值，也就是比较值等于5。使用比较值5与第j-1个元素(也就是第0个元素)进行比较，5<6,所以第j个元素(也就是第1个元素)，赋值为6,得到以下结果[ 6 6 1 7 3 ]。此时j-=1,j=0,退出内部循环，所以第o个元素赋值为compare_value，也就是5,得到以下结果[ 5 6 1 7 3 ],这样就完成了一层外部循环，而没有采用一次数据的交换。然后依此类推，完成排序。这样我们就做到了，减少数据交换的次数来提升执行效率的目的了。

下面，我用一个数组长度为10000，数组中的元素范围在0-10000的随机数组作为测试用例，来测试一下，以上三种插入排序方式各自完成排序所需要的时间情况。