//从第一个元素开始,该元素可以认为已经被排序;
// 取出下一个元素,在已经排序的元素序列中从后向前扫描;
// 如果该元素(已排序)大于新元素,将该元素移到下一位置;
// 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
// 将新元素插入到该位置后;
// 重复步骤2~5。

//时间复杂度:最好的情况原本就是有序O(n) 最坏的情况 O(n的平方) 平均O(n的平方)
//空间复杂度:O(1)
        var arr = [52,46,16,45,88,20,8,72];
        function DirectInsertionSort(arr){
            var len = arr.length;
            var temp;
            for(var i=1;i<arr.length;i++){
                temp = arr[i]; 
                j = i-1
                while(j>=0&&temp<arr[j]){
                    arr[j+1] = arr[j];
                    j--;
                }
                arr[j+1] = temp; 
            }
            return arr;
        }
        console.log(DirectInsertionSort(arr));//8,16,20,45,46,52,72,88