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

7,440 阅读2分钟
原文链接: yuzmb.github.io

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

冒泡排序:

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

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()合并,再进行比较,如此反复

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);//截取中间值
  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()方法:简单粗暴

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

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

方法一:

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();

方法二

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)

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

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

(完)