02插入排序-javascript

算法原理

• 插入排序的基本操作将一个数据插入到已经排好的有序数据中，从而得到一个新的数组，个数加一的有序数

算法特点

• 插入算法把要排序的数组分两部分：第一部分包含了这个数组的所有元素，但将第一个元素除外（让数组多一个空间才有插入的位置）第二部分就是包含这个元素（即待插入的元素）。在第一部分排序完成后，将这个最后插入到已排好序的第一部分中
• 比冒泡排序更快些

代码实现

  function insertSort(arr){
      for ( var i = 1; i < arr.length; i++ ){
        //从第一个数开始遍历到最后一个数
         var f = arr[i];
          //每次i - 1 表示在当前f之前的所有数，跟f 进行比较，也就是 右边的数跟左边以此比较， 如果左边比右边大，就让 左边的跟右边 j 交换，
          for ( var j = i-1; arr[j] > f; j-- ){
            //arr[j+1]实际上代表的是f ，为什么不直接用f，这里需要细心看看，f是需要跟 arr[j] 以此比较的，如果条件满足就交换，次数的 f值会跟左边的数交换
             arr[j+1] = arr[j]
         }
         if ( arr[j+1] !=f ){
            arr[j+1] = f
          }
      }
      return arr
   }
var arr = [2,3,6,4,2,1,90,100,20,5]
console.log( insertSort(arr).join(',') )