笔试中经常出现的js数组排序与去重算法

JavaScript
  view

数组排序比较常用的：冒泡排序、快速排序、sort()方法排序；数组去重方法也有很多。

冒泡排序：

从数组中随便拿一个数与后一位比较，如果前者比后者大，那么两者交换位置，从而遍历数组可以得到排序的效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var arr = [1, 9, 4, 50, 49, 6, 3, 2];
function test(){
  for (var i = 0; i < arr.length - 1; i++){
    for (var j = i + 1; j < arr.length; j++){
      var tempi = arr[i]; //获取第一个值，并与后一个值比较
      var tempj = arr[j];
      if (tempi > tempj){
        arr[i] = tempj;
        arr[j] = tempi;//如果前一个值比后一个值大，那么相互交换
      }
    }
  } 
  console.log(arr); //return arr；
}
test();//调用函数

快速排序：

在数组中间那一个值，然后用这个值跟数组里面的值相比较，大于此值的放在一边，小于的也放在一边，然后用concat()合并，再进行比较，如此反复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var arr = [1, 9, 4, 50, 49, 6, 3, 2];
function test(arr){
  if (arr.length <= 1) return arr;//如果数组只有一位，就没有必要比较了
  var index = Math.floor(arr.length / 2);//获取中间值的索引
  var cur = arr.splice(index, 1);//截取中间值，如果此处使用cur=arr[index]; 那么将会出现无限递归的错误
  var left = [], right = [];//小于中间值的放在left数组里，大于的放在right数组
  for (var i = 0; i < arr.length; i++){
    if (cur > arr[i]){
      left.push(arr[i]);
    } else{
      right.push(arr[i]);
    }
  }
  return test(left).concat(cur, test(right));//通过递归，上一轮比较好的数组合并，并且再次进行比较
}
test(arr);

sort()方法：简单粗暴

1
2
3
4
5
6
7
8
9
10
11
var arr = [1, 9, 4, 50, 49, 6, 3, 2];
function test(){
  return arr.sort(sortNumber);
}
function sortNumber(a, b){
  return a - b;
}
test();

笔者常用的数组去重方法：

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
var arr = [1, 'a', 'a', 'b', 'd', 'e', 'e', 1, 0]
function test(){
  for (var i = 0; i < arr.length; i++){
    for(var j = i + 1; j < arr.length; j++){
      if(arr[i] === arr[j]) arr.splice(j,1);//如果前一个值与后一个值相等，那么就去掉后一个值，splice()可以修改原数组
    }
  }
  return arr;
}
test();

方法二

1
2
3
4
5
6
7
8
9
10
11
var arr = [1, 1, 4, 50, 50, 6, 2, 2];
function test(){
  return arr.filter(function(item,index,array){
    return array.indexOf(item) === index; 
    //或者这样写return array.indexOf(item, index+1) === -1; 如果没有重复项，返回true
    //用filter方法，返回ietm对应的indexOf索引值与本身index索引值相等的值，也就是去掉重复的值，filter本身不修改数组，只是会自动遍历数组，去掉重复值后，那么arr就剩下不重复的了
  });
}
test();//输出Array [ 1, 4, 50, 6, 2 ]

方法三(ES6)

1
2
3
4
5
6
7
var arr = [1, 1, 4, 50, 50, 6, 2, 2];
function unique(arr){
  return Array.from(new Set(arr));
}
unique(arr);

还有一些方法，我也没用过，前两种是笔者经常用的~~

(完)