【手撕代码7】排序算法，查找

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

交换（使用解构赋值）

arr1=[1,2];
arr2=[2,3];
[arr1,arr2]=[arr2,arr1];
console.log(arr1);//2,3

检查是否为数组，交换位置

function checkArr(arr){
  return Array.isArray(arr);
}
function swap(arr,left,right){
  [arr[left],arr[right]]=[arr[right],arr[left]];
}

冒泡排序

• 冒泡排序的原理如下，从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素，那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作，但是此时最后一个元素已经是最大数了，所以不需要再比较最后一个元素，只需要比较到 length - 2 的位置。

function bubble(arr){
  if(!checkArr(arr)){
    console.log("not arr");
  }
  for(let i=0;i<arr.length-1;i++){
    //写在第一个for循环里，是为了，每轮比较初始化bool变量变为true。
    let flag=true;
    for(let j=0;j<arr.length-1-i;j++){//每一轮都会比较出一个最大值，然后后一轮没有必要再比较了，所以没比较一轮，就少比较一次
      if(arr[j]>arr[j+1]){
        swap(arr,j,j+1);
        flag=false
      } 
    }
    if(flag){//，如果本轮比较没有任何元素相互交换位置，那么说明已经比较完成，可以跳出循环
    break;
    }
  }
  return arr;
}
var arr=[2,1,5,6,3];
console.log(bubble(arr));

• 该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(n * n)

选择排序

• 选择排序的原理如下。遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。

function select(arr){
  if(!checkArr(arr)){
    console.log("not arr");
  }
  for(let i=0;i<arr.length-1;i++){
      let minindex=i;
    for(j=i+1;j<arr.length;j++){
      minindex=arr[j]<arr[minindex]?j:minindex;
      }
    swap(arr,i,minindex);
    
  }
  return arr;
}
var arr=[2,1,5,6,3];
console.log(select(arr));

快排

var quickSort = function(arr) {

　　if (arr.length <= 1) { return arr; }

　　var pivotIndex = Math.floor(arr.length / 2);

　　var pivot = arr.splice(pivotIndex, 1)[0];

　　var left = [];

　　var right = [];

　　for (var i = 0; i < arr.length; i++){

　　　　if (arr[i] < pivot) {

　　　　　　left.push(arr[i]);

　　　　} else {

　　　　　　right.push(arr[i]);

　　　　}

　　}

　　return quickSort(left).concat([pivot], quickSort(right));

};

归并排序

• 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

function mergeSort(arr){
  //设置终止的条件
  if(arr.length<2){
    return arr;
  }
  //设置中间值
  var middle=Math.floor(arr.length/2);
  var left=arr.slice(0,middle);
  var right=arr.slice(middle);
  if(left=="undefined"&&right=="undefined"){
    return false;
  }
  return merge(mergeSort(left),mergeSort(right));
}
function merge(left,right){
    var result=[];
    while(left.length&&right.length){
      if(left[0]<=right[0]){
        result.push(left.shift());
      }else{
        result.push(right.shift());
      }
    }
    while(left.length){
      result.push(left.shift());
    }
    while(right.length){
      result.push(right.shift());
    }
  return result;
}

// 测试数据
var nums=[6,10,1,9,4,8,2,7,3,5];
console.log(mergeSort(nums));

image

二分查找

• 二分查找，折半查找（有序数组中查找特定元素）
• 首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。
• 如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。
  //如果某一步数组为空，则表示找不到目标元素

//二分查找，折半查找（有序数组中查找特定元素）
//首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。
//如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。
//如果某一步数组为空，则表示找不到目标元素。
function binSearch(arr,data){
  var low=0;
  var high=arr.length-1;
   while(low<=high){
     var middle=Math.floor((low+high)/2);
     if(arr[middle]<data){
       low=middle+1;
     }else if(arr[middle>data]){
       high=middle-1;
     }else{
       return middle;
     }
   }
  return -1;
}
var arr=[3,6,9,10,70];
console.log(binSearch(arr, 10))