[数据结构与算法]【 总结 】插入排序

插入排序

每次排一个数组项，假设数组的第一项已经排序，接着，把第二项与第一项进行对比，第二项是该插入到第一项之前还是之后，第三项是该插入到第一项之前还是第一项之后还是第三项

		var array = [5,2,8,7,3,6,4,1,9]
		function insertionSort(array){
		   let tmp
           let j 
           for(let i = 1 ; i < array.length ; i++){
              j = i - 1;
              // 记录无序数组的数据的第一个元素
              tmp = array[i]
              while(j>=0 && tmp < array[j]){
                  array[j+1] = array[j]
                  j--
              }
              array[j+1] = tmp
           }
           return array
		}
		console.log(insertionSort(array))
		// [1, 2, 3, 4, 5, 6, 7, 8, 9]