直接插入排序（扑克牌排序）

我们在打扑克牌的时候，抓牌的时候，我们喜欢从小到大进行排列，如果新抓到一个扑克牌，我们会把它插入到已经整理好的扑克牌中间，也就是插入之后，扑克牌的顺序还是从小到大排列的。

原理：将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

时间复杂度
每次需要从无序数列中去一个数和有序数列比较，然后插入，因此理论上需要两层循环，也就是时间复杂度为O(n^2)

<?php

function insert_sort($arr)
{
    //区分哪部分是已经排序好的
    //哪部分是没有排序的
    //找到其中一个需要排序的元素
    //这个元素就是从第二个元素开始，到最后一个元素都是这个需要排序的元素
    //利用循环就可以标志出来
    //i循环控制每次需要插入的元素，一旦需要插入的元素控制好了，
    //间接已经将数组分成了2部分，下标小于当前的（左边的），是排序好的序列
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        //获得当前需要比较的元素值。
        $tmp = $arr[$i];
        //内层循环控制比较并插入
        for ($j = $i - 1; $j >= 0; $j--) {
            //$arr[$i];//需要插入的元素;$arr[$j];//需要比较的元素
            if ($tmp < $arr[$j]) {
                //发现插入的元素要小，交换位置
                //将后边的元素与前面的元素互换
                $arr[$j + 1] = $arr[$j];
                //将前面的数设置为当前需要交换的数
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素
                //由于是已经排序好是数组，则前面的就不需要再次比较了。
                break;
            }
        }
    }
    //将这个元素插入到已经排序好的序列内。
    //返回
    return $arr;
}

$arr = array(8, 4, 6, 3, 9, 1, 7, 2);

$sort_arr = insert_sort($arr);

print_r($sort_arr);

print_R($sort_arr);