前端面试 - 算法

https://www.cnblogs.com/tine/p/5938844.html
时间复杂度：一个算法执行所消耗的时间
空间复杂度：运行完一个程序所需内存的大小

• 选择排序：
  两个for循环嵌套，外循环记录每次循环开始的位置，内循环查找本次循环内的最小值；
  实质是每循环一次将查到的最小值放在每次循环的最初开始的位置；
  [先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。]

function arrSort(arr) {
 var len = arr.length
 var minIndex,temp;
 for(var i = 0;i<len-1;i++){ //遍历次数
     minIndex = i; //每次循坏的第一个数为最小的
     for(var j = i+1;j<len;j++){ //遍历个数
        if(arr[j] < arr[minIndex]) {
         minIndex = j；找到每次循环到的最小值
         }
     }
       temp = arr[i]
       arr[i] = arr[minIndex]；//将找到的最小值放在每次循环的最开始的地方
       arr[minIndex] = temp
   }
   return arr
}
----------------------------------------
var temp;
for(var i = 0;i<arr.length-1;i++){
   for(var j = i+1;j<arr.length-1;j++){
         if(arr[i]>arr[j]) {
             temp = arr[j];
             arr[j] = arr[i];
             arr[i] = temp 
         }
     }
}

• 冒泡排序
  依次比较相邻的两个值，如果后面的比前面的小，则将小的元素排到前面。依照这个规则进行多次并且递减的迭代，直到顺序正确。

function BubbleSort(arr){
let len = arr.length  
for(var i = 0;i<len-1;i++){
    for(var j =0;j<len-1-i;j++){
       if(arr[j]>arr[j+1])
          var temp = arr[j]
          arr[j] = arr[j+1]
          arr[j+1] = temp
    }
  }
}
return arr

• 插入排序 快速排序
  二分查找 元素必须是有序的，否则先进行排序

// 递归方法：
function binararySearch（data,item,start,end）{
var start = start || 0;
var end = end || data.length-1
var middle = Math.floor((start+end)/2)
if(item == data[middle]){
  return middle
}else if(item <  data[middle]) {
    return binararySearch(data,item,start,middle-1)
}else{
  return binararySearch(data,item,middle+1,end)
    }
 return false;
}

// 非递归方法
function binarySearch(data, item){
      var h = data.length - 1,
          l = 0;
         while(l <= h){
          var m = Math.floor((h + l) / 2);
          if(data[m] == item){
              return m;
          }
          if(item > data[m]){
             l = m + 1;
         }else{
             h = m - 1;
         }
     }
     return false;
 }
```