JS 常见算法积累（一）

发表于   |   分类于

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

数组去重

  • 先来说说比较容易想到的方法：
1
2
3
4
5
6
7
8
9
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来进行筛选:
1
2
3
4
5
6
7
8
9
10
11
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;
}
  • 排序后去重：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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')))

取数组中最大差值

  • 该方法很容易想到，就是找到最大的值减去最小的值即可得到：
1
2
3
4
5
6
7
8
9
10
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，直到排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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）
  • 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边
  • 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)); //返回左边数组+基准值+右边数组
}