JS常问算法

扁平化数组

Object.assign(Array.prototype, {
    // 扁平化数组
    myFlat() {
        return this.reduce( (res, cur) =>{
            return Array.isArray(cur) ? res.concat(cur.myFlat()) : res.concat(cur)
        },[])
    }
})
let arr = [1, [2, [3, 4], 5], 6]
console.log(arr.myFlat())

数组去重

Object.assign(Array.prototype, {
    // 数组去重
    unique(){
        let newArr = [this[0]];
        for(let i=1; i<this.length; i++){
            if(newArr.indexOf(this[i]) === -1){
                newArr.push(this[i])
            }
        }
        return newArr;
    }
})
let arr2 = [1,2,2,3,4,4,5]
console.log(arr2.unique())

冒泡排序(bubbleSort)

冒泡排序是最慢的排序算法。在实际运用种它是效率最低的算法！O(n^ 2)

<script type="module">
Object.assign(Array.prototype, {
    // 冒泡排序
    bubbleSort(){
        for(let i=0, len=this.length; i<len; i++){
            const left = this[i-1];
            const right = this[i];
            if(left > right){
                this[i-1] = right;
                this[i] = left;
                i = 0
            }
        }
        return this;
    }
})
let arr3 = [3,5,6,2,1,4]
console.log(arr3.bubbleSort())
</script>

快速排序(quickSort)

快速排序比大部分排序算法都要快、但是对于内存非常有限的机器来说、他不太适合！

<script type="module">
Object.assign(Array.prototype, {
    // 快速排序
    quickSort(){
        if(this.length <= 1) return this;
        const pivotIndex = Math.floor(this.length/2);
        const pivot = this.splice(pivotIndex, 1)[0];
        const left = [];
        const right = [];
        for(let i=0; i<this.length; i++){
            let v = this[i];
            if(v <= pivot){
                left.push(v)
            }else{
                right.push(v)
            }
        }
        return left.quickSort().concat([pivot], right.quickSort())
    }
})
let arr4 = [3,5,6,2,1,4]
console.log(arr4.quickSort())
</script>

插入排序（insertSort)

插入排序通过把序列中的值插入一个已经排序改的序列中、知道改序列的结束！插入排序是对冒泡排序的改进、他比冒泡排序快二倍、一般用于数据低于1000的场景下使用、或者重复排序超过200数据项的序列

<script type="module">
  Object.assign(Array.prototype, {
      // 插入排序
      insertSort(){
          const _searchIndex = function(arr, x){
              if(x <= arr[0]) return 0;
              if(x >= arr[arr.length-1]) return arr.length;
              let i = 0;
              for(; i<arr.length; i++){
                  if(arr[i] <= x && x <= arr[i + 1]){
                      break;
                  }
              }
              return i + 1;
          }
          let sortArr = [this[0]];
          for(let i=1; i<this.length; i++){
              let index = _searchIndex(sortArr, this[i]);
              sortArr.splice(index, 0, this[i]);
          }
          return sortArr;
      }
  })
  let arr4 = [3,5,6,2,1,4]
  console.log(arr4.insertSort())
</script>

斐波那契数列

function getFibonacci(n){
  const arr = [];
  for(let i=0; i<n-1; i++){
    if(i<=1){
      arr.push(1)
    }else{
      arr.push(arr[i-1] + arr[i-2])
    }
  }
  return arr;
}
console.log(getFibonacci(10))