2019-08-11

Javascript中常用几种基础算法

1 排序-冒泡排序

   //冒泡排序

function bubbleSort(arr) {

    let len = arr.length;

    if(!len){

      return;

    }

    for(let i = 1, i < len - 1; ++i) {

      for(let j = 0; j <= len - i; ++j) {

        if (arr[j] > arr[j + 1]) {

          let temp = arr[j];

          arr[j] = arr[j + 1];

          arr[j + 1] = temp;

        }

      }

    }

}

2 插入排序

//插入排序

function insertionSort(arr) {

    const n = arr.length;

    // 从arr[0]已经被排序，所以i从1开始

    for (let i = 1; i < n; i++) {

      for (let j = i - 1; j >= 0; j--) {

        if (arr[i] >= arr[j]) {

          arr.splice(j + 1, 0, arr.splice(i, 1)[0]);

          break; 

        } else if (j === 0) {

          arr.splice(j, 0, arr.splice(i, 1)[0]);

        }

      }

    }

    return arr;

  }

3 快速排序

//快速排序

function qSort(arr) {

    //声明并初始化左边的数组和右边的数组

    let left = [], right = [];

    //使用数组第一个元素作为基准值

    var base = arr[0];

    //当数组长度只有1或者为空时，直接返回数组，不需要排序

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

    //进行遍历

    for(var i = 1, len = arr.length; i < len; i++) {

      if(arr[i] <= base) {

      //如果小于基准值，push到左边的数组

        left.push(arr[i]);

      } else {

      //如果大于基准值，push到右边的数组

        right.push(arr[i]);

      }

    }

    //递归并且合并数组元素

    return [...qSort(left), ...[base], ...qSort(right)];

  }