javascript的算法

2018-02-08 本文已影响0人那个大螺丝

用JS写算法的作用？

锻炼思维，提高开发效率。
~~虽然平时工作不一定能用到，但是面试的时候吹逼很有用。~~

函数式编程有啥用？

更短的代码、更少的BUG。
~~函数式编程这个名词比较装逼。~~

冒泡排序

冒泡排序是所有排序算法里最简单的一个，（但是从效率来讲是最差的一个，时间复杂度为O(n^2)）。
冒泡排序会以此比较任何相邻的元素，如果第一个比第二个大，则交换他们。
较小的元素不断向前排列，就像轻的气泡上升一样，所以叫冒泡排序。
每一次循环遍历数组的时候，元素只会向前移动一个位置，所以如果要保证所有元素正确排序，
比如最小的元素在原数组的最后，需要排到最前，需要循环套循环，才能保证排序正确。

 //函数式版
const bubbleSort = (array)=>{
  return array.reduce((pre)=>{
    return pre.reduce((p,c,i,arr)=>{
      if(arr[i]>arr[i+1]){
        [arr[i],arr[i+1]]=[arr[i+1],arr[i]];
      }
      return arr
    },[]);
  },[...array]);
};

//命令式版
const bubbleSort = (array) =>{
  for(let i=0; i<array.length; i++){
    for(let i=0; i<array.length; i++){
      if(array[i]>array[i+1]){
        [array[i],array[i+1]]=[array[i+1],array[i]]
      }
    }
  }
};

选择排序

选择排序的原理是，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

每次循环遍历数组只能找到1个元素并排序，所以和冒泡排序一样，需要循环套循环才能保证排序正确，时间复杂度也是O(n^2)。

// 函数式版
const selectionSort = (array)=>{
  return array.reduce((pre,cur,index)=>{
    return pre.reduce((_pre,_cur,_index,arr)=>{
      if(_index>=index && arr[_index]<arr[index]){
        [arr[_index],arr[index]]=[arr[index],arr[_index]]
      }
      return arr;
    },[])
  },[...array])
};

//命令式版
const selectionSort = (array)=>{
  const length = array.length;
  let indexMin;
  for(let i=0; i<length-1; i++){
    indexMin = i;
    for(let j=i;j<length;j++){
      if(array[indexMin]>array[j]){
        indexMin = j;
      }
    }
    if(i !== indexMin){
     [array[indexMin],array[i]] = [array[i],array[indexMin]]
    }
  }
};

插入排序

插入排序的工作原理是，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。时间复杂度也是O(n^2)

//函数式版
const insertionSort = (array) =>{
  return array.reduce((pre,cur)=>{
    return [...pre,cur].reduce((_pre,_cur,index,arr)=>{
      const last = arr.length - index-1;
      const _last = arr.length - index - 2;
      if(arr[last] < arr[_last]){
        [arr[last], arr[_last]] = [arr[_last], arr[last]];
      }
      return arr
    },[])
  },[])
};

//命令式版
const insertionSort = (array)=>{
  const length = array.length;
  let j,temp;
  for(let i=1; i<length; i++){
    j=i;
    temp = array[i];
    while(j>0 && array[j-1]>temp){
      array[j] = array[j-1];
      j--;
    }
    array[j] = temp;
  }
};

归并排序

前三个排序算法性能不好，但归并排序性能不错，是一个可以被实际使用的排序算法,时间复杂度为O(nlogn)，但是会比前三种算法难一些。
归并排序的是一种分治算法,意思就是把数组分成较小的数组，直到每个数组只有一个元素，然后对小数组逐级往上合并排序一个大数组，
直至所有排序完成。

//函数式版
const mergeSort = (array) => {
  if(array.length < 2) return array;
  return merge(
    mergeSort(array.splice(0,Math.floor(array.length/2))),
    mergeSort(array)
  );
};

const merge = (left, right)=> {
  return [...left,...right].reduce((pre)=>{
    if(left[0]<right[0] || !right[0] ){
      return [...pre,left.shift()]
    }else{
      return [...pre,right.shift()]
    }
  },[]);
};

 //命令式版
const mergeSort = (array)=>{
  const length = array.length;
  if(length === 1){
    return array;
  }
  const mid = Math.floor(length/2),
    left = array.slice(0,mid),
    right = array.slice(mid, length);
  return merge(mergeSort(left), mergeSort(right))
};

const merge = (left,right)=>{
  const result = [];
  let il=0,ir=0;
  while(il<left.length && ir < right.length){
    if(left[il]<right[ir]){
      result.push(left[il++]);
    }else{
      result.push(right[ir++]);
    }
  }
  while(il<left.length){
    result.push(left[il++]);
  }
  while(ir<right.length){
    result.push(right[ir++]);
  }
  return result;
};

快速排序

快速排序是最常用的排序算法了，它的复杂度为O(nlogn)，和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组。

在这个排序中，函数式版和命令式版略为不同。

函数式版的思想为，每次抽取数组的第一号元素，剩下的元素中，把比一号元素小的都放在一号元素的左边，剩下的放在右边，组成一个新的数组。
并且对剩下的大/小数组进行递归，直至完成排序。这个排序算法比node原生的排序都要快，有兴趣的朋友可以试试。详情请撸以下代码。

//函数式版
const quick_sort =(array)=> {
  if(array.length < 2) return array;
  const arr = array.reduce((pre,cur,index)=>{
    if(cur<array[0] && index !==0){
      pre.left.push(cur);
      return pre ;
    }else if(cur >= array[0] && index !==0){
      pre.right.push(cur);
      return pre;
    }
    return pre;
  },{left:[],right:[]});
  return [...quick_sort(arr.left), array[0], ...quick_sort(arr.right)]
};

命令式版的思想为

首先，从数组中选择中间一项作为主元。
创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。
移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交
换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之
前，而比主元大的值都排在主元之后。这一步叫作划分操作。
接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的
子数组）重复之前的两个步骤，直至数组已完全排序。

//命令式版
const quick = (array,left,right)=>{
  let index;
  if(array.length>1){
    index = partition(array,left,right);
    if(left < index -1){
      quick(array, left, index -1);
    }
    if(index<right){
      quick(array, index, right);
    }
  }
  return array
};

const partition = (array, left, right) =>{
  const pivot = array[Math.floor((left+right)/2)];
  let i = left,
    j = right;
  while(i<=j){
    while(array[i]<pivot){
      i++;
    }
    while(array[j]>pivot){
      j--;
    }
    if(i<=j){
      [array[i],array[j]]=[array[j],array[i]];
      i++;
      j--;
    }
  }
  return i;
};