直接插入排序

//从第一个元素开始，该元素可以认为已经被排序；
// 取出下一个元素，在已经排序的元素序列中从后向前扫描；
// 如果该元素（已排序）大于新元素，将该元素移到下一位置；
// 重复步骤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