JS 常见算法积累（一）

[Hancoson]

算法技能如今越来越被看重，今天开始把平时记录的一些关于JS算法的题目做一下记录，弥补自己在这一项的缺陷。

数组去重

• 先来说说比较�容易想到的方法：

function unique(arr){
  var newArr = [];
  for(var i = 0;i<arr.length;i++){
    if(newArr.indexOf(arr[i]) === -1){
      newArr.push(arr[i])
    }
  }
  return newArr
}

该方中的indexOf兼容性需要考虑;

• 利用Object中key的唯一性，利用key来进行筛选:

function unique(arr){
  var obj = {}
  var data = []
    for(var i in arr){
      if(!obj[arr[i]]){
        obj[arr[i]] = true;
        data.push(arr[i]);
      }
    }
  return data;
}

• 排序后去重：

function unique(arr){
  var newArr = [];
  arr.sort();
	for(var i=0;i<arr.length;i++){
    if(i===0){
      newArr.push(arr[i])
    }
    else{
      if(arr[i]!==arr[i-1]){
        newArr.push(arr[i])
      }
    }
  }
  return newArr;
}

该方法会打乱原有数组的顺序；

对象根据属性排序

• arrayObject.sort(sortby)，sortby非必填但必须为一个函数，规定排序顺序。这里嵌套一层函数用来接收对象属性名，其他部分代码与正常使用sort方法相同：

如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值，然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b，其返回值如下：

• 若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。
• 若 a 等于 b，则返回 0。
• 若 a 大于 b，则返回一个大于 0 的值。

var arr = [
  {name:'zopp',age:0},
  {name:'gpp',age:18},
  {name:'yjj',age:8}
];

function compare(property){
  return function(a,b){
    var value1 = a[property];
    var value2 = b[property];
    return value1 - value2;
  }
}
console.log(arr.sort(compare('age')))

取数组中最大差值

• 该方法很容易想到，就是�找到最大的值减去最小的值即可得到：

function getMax(arr){
  var min = arr[0];
  var max = arr[0];  //先假定第一个值及时最大也是最小的
  for(var i = 0;i<arr.length;i++){
    if(arr[i]<min) min = arr[i]

    if(arr[i]>max) max = arr[i]
  }
  return max - min
}

排序

�动画演示

冒泡排序

• 比较简单的排序算法，说白了就是把相邻的两个元素拿来比较大小并重复进行，如果后面的比前面的小，把�小的放在前面。
• 时间复杂度：O(n2)
• 具体算法描述如下：
  • 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  • 针对所有的元素重复以上的步骤，除了最后一个；
  • 重复步骤1~3，直到排序完成。

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

选择排序

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
• 时间复杂度：O(n2)

function findMin(arr,first){
  var minIndex = first; //定义最小下标
  var minNum = arr[first]; //定义数组中的最小值
  for(var i=first+1;i<arr.length;i++){
    if(arr[i]<minNum){
      minIndex = i;
      minNum = arr[i]
    }
  }
  return minIndex; //返回最小的下标
}

function selectionSort(arr){
  for(var i = 0;i<arr.length;i++){
    var min = findMin(arr,i);
    var temp = arr[min];
    arr[min] = arr[i];
    arr[i] = temp;
  }
  return arr;
}

快速排序

• 在数据集之中，选择一个元素作为"基准"（pivot）
• 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边
• 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止

function quickSort(arr){
  if(arr.length <=1){
    return arr;
  }
  else{
    var pivotIndex = Math.floor(arr.length/2); //找基准值，一般取中间项
    var pivot = arr.splice(pivotIndex,1)[0]; //删除原来的基准值
    var left = [],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)); //返回左边数组+基准值+右边数组
}