一、原理

        指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

二、实现

    1、PHP

        function insertSort($arr)
        {
            if (!is_array($arr)) {
                return [];
            }
            $n = count($arr);
            if ($n === 1) {
                return $arr;
            }
            // $arr[0] 是已排序好的数组
            for ($i = 1; $i < $n; $i ++) {
                $is = $arr[$i]; // 要插入的值
                $j = $i - 1; // 从后往前比较
                while($j > 0 && $is < $arr[$j]) {
                    $arr[$j + 1] = $arr[$j];
                    $j--;
                }
                $arr[$j + 1] = $is;
            }
            return $arr;
        }

    2、javascript

        function insertSort(arr)
        {
            if (!Array.isArray(arr)) {
                return [];
            }
            var len = arr.length;
            if (len <= 1) {
                return arr;
            }
            // arr[0]为已排序数组
            for (var i = 1; i < len; i ++) {
                var is = arr[i];
                var j = i - 1;
                while(j >= 0 && is < arr[j]) {
                    arr[j + 1] = arr[j];
                    j --;
                }
                arr[j + 1] = is;
            }
            return arr;
        }

    3、时间复杂度

    最小为O(n), 最大为O(n^2)

    4、稳定性

    稳定