2019面试 JS排序和数组去重有哪些方法?_Coderfei的专栏文章_微信文章

数组的排序和去重，一直是面试中的一个热点，一般是要求手写数组去重方法的代码，因为它能够很好地考察一个人的逻辑思维能力。如果是被提问到，数组去重的方法有哪些？你能答出其中的10种，面试官很有可能对你刮目相看。这些知识只要经过一定地刻意训练，多看，多思考，多敲代码，这些算法的掌握其实是一件很简单的事情。
全文分为两部分，数组的排序和数组的去重。

一. 数组去重

1、建立一个空的数组

var arr=[11,22,33,44,55,22,22,33,54];//拿到数组中不重复的元素
var x=[];  //定义一个空数组
for(var n=0;n<arr.length;n++){
    if (x.indexOf(arr[n])==-1){
        x.push(arr[n]);//怎么判断新的数组中是否有arr[n]这个元素呢；
    }
}
console.log(x.sort());复制代码

2、用 indexOf( )

var arr=[11,22,33,44,55,22,33,54];
for(var n=0;n<arr.length;n++){
	for(var j=n+1;j<arr.length;j++){
		if (arr[n]==arr[j]) {
			arr.splice(arr.indexOf(arr[j]),1);
			j--;
		}
	}
}
console.log(arr)复制代码

var arr=[11,22,33,44,55,22,33,54];
for(var n=0;n<arr.length;n++){
	if (arr.indexOf(arr[n])!=arr.lastIndexOf(arr[n])){
		//判断arr[n]出现的次数，如果次数不是一次，那么删除后边的元素
		arr.splice(arr.lastIndexOf(arr[n]),1);
		n--;//没有这个n--，相当于执行了8次，
	}
}
console.log(arr);复制代码

3、利用ES6 Set去重（ES6中最常用）

function unique (arr) {
  return Array.from(new Set(arr))
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
 //[1, "true", true, 15, false, undefined, null, NaN, "NaN", 0, "a", {}, {}]复制代码

不考虑兼容性，这种去重的方法代码最少。这种方法还无法去掉“{}”空对象，后面的高阶方法会添加去掉重复“{}”的方法。

4、利用for嵌套for，然后splice去重（ES5中最常用）

function unique(arr){            
        for(var i=0; i<arr.length; i++){
            for(var j=i+1; j<arr.length; j++){
                if(arr[i]==arr[j]){         //第一个等同于第二个，splice方法删除第二个
                    arr.splice(j,1);
                    j--;
                }
            }
        }
return arr;
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "true", 15, false, undefined, NaN, NaN, "NaN", "a", {…}, {…}]     
//NaN和{}没有去重，两个null直接消失了复制代码

双层循环，外层循环元素，内层循环时比较值。值相同时，则删去这个值。

5、也是利用indexOf去重

function unique(arr) {
    if (!Array.isArray(arr)) {
        console.log('type error!')
        return
    }
    var array = [];
    for (var i = 0; i < arr.length; i++) {
        if (array .indexOf(arr[i]) === -1) {
            array .push(arr[i])
        }
    }
    return array;
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
   // [1, "true", true, 15, false, undefined, null, NaN, NaN, "NaN", 0, "a", {…}, {…}]  //NaN、{}没有去重复制代码

新建一个空的结果数组，for 循环原数组，判断结果数组是否存在当前元素，如果有相同的值则跳过，不相同则push进数组。

6、利用sort()

function unique(arr) {
    if (!Array.isArray(arr)) {
        console.log('type error!')
        return;
    }
    arr = arr.sort()
    var arrry= [arr[0]];
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] !== arr[i-1]) {
            arrry.push(arr[i]);
        }
    }
    return arrry;
}
     var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
        console.log(unique(arr))
// [0, 1, 15, "NaN", NaN, NaN, {…}, {…}, "a", false, null, true, "true", undefined]      
//NaN、{}没有去重复制代码

利用sort()排序方法，然后根据排序后的结果进行遍历及相邻元素比对。

7、利用对象的属性不能相同的特点进行去重（这种数组去重的方法有问题，不建议用，有待改进）

function unique(arr) {
    if (!Array.isArray(arr)) {
        console.log('type error!')
        return
    }
    var arrry= [];
     var  obj = {};
    for (var i = 0; i < arr.length; i++) {
        if (!obj[arr[i]]) {
            arrry.push(arr[i])
            obj[arr[i]] = 1
        } else {
            obj[arr[i]]++
        }
    }
    return arrry;
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "true", 15, false, undefined, null, NaN, 0, "a", {…}]    
//两个true直接去掉了，NaN和{}去重复制代码

8、利用includes

function unique(arr) {
    if (!Array.isArray(arr)) {
        console.log('type error!')
        return
    }
    var array =[];
    for(var i = 0; i < arr.length; i++) {
            if( !array.includes( arr[i]) ) {//includes 检测数组是否有某个值
                    array.push(arr[i]);
              }
    }
    return array
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "true", true, 15, false, undefined, null, NaN, "NaN", 0, "a", {…}, {…}]     
//{}没有去重复制代码

9、利用hasOwnProperty

function unique(arr) {
    var obj = {};
    return arr.filter(function(item, index, arr){
        return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)
    })
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "true", true, 15, false, undefined, null, NaN, "NaN", 0, "a", {…}]   
//所有的都去重了复制代码

利用hasOwnProperty 判断是否存在对象属性

10、利用filter

function unique(arr) {
  return arr.filter(function(item, index, arr) {
    //当前元素，在原始数组中的第一个索引==当前索引值，否则返回当前元素
    return arr.indexOf(item, 0) === index;
  });
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "true", true, 15, false, undefined, null, "NaN", 0, "a", {…}, {…}]复制代码

11、利用递归去重

function unique(arr) {
        var array= arr;
        var len = array.length;

    array.sort(function(a,b){   //排序后更加方便去重
        return a - b;
    })

    function loop(index){
        if(index >= 1){
            if(array[index] === array[index-1]){
                array.splice(index,1);
            }
            loop(index - 1);    //递归loop，然后数组去重
        }
    }
    loop(len-1);
    return array;
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "a", "true", true, 15, false, 1, {…}, null, NaN, NaN, "NaN", 0, "a", {…}, undefined]复制代码

12、利用Map数据结构去重

function arrayNonRepeatfy(arr) {
  let map = new Map();
  let array = new Array();  // 数组用于返回结果
  for (let i = 0; i < arr.length; i++) {
    if(map .has(arr[i])) {  // 如果有该key值
      map .set(arr[i], true); 
    } else { 
      map .set(arr[i], false);   // 如果没有该key值
      array .push(arr[i]);
    }
  } 
  return array ;
}
 var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
    console.log(unique(arr))
//[1, "a", "true", true, 15, false, 1, {…}, null, NaN, NaN, "NaN", 0, "a", {…}, undefined]复制代码

创建一个空Map数据结构，遍历需要去重的数组，把数组的每一个元素作为key存到Map中。由于Map中不会出现相同的key值，所以最终得到的就是去重后的结果。

13、利用reduce+includes

function unique(arr){
    return arr.reduce((prev,cur) => prev.includes(cur) ? prev : [...prev,cur],[]);
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr));
// [1, "true", true, 15, false, undefined, null, NaN, "NaN", 0, "a", {…}, {…}]复制代码

14、[...new Set(arr)]

[...new Set(arr)] 
//代码就是这么少----（其实，严格来说并不算是一种，相对于第一种方法来说只是简化了代码）复制代码

二. 多维数组的操作

综合拓展：多维数组化为一维数组，然后进行去重，排序，

function f (arr) {            
    if (Object.prototype.toString.call(arr) !='[object Array]') {//判断是否为数组                
        return;            
    }            
    var newarr = [];            
    function fn (arr) {                
        for (var i = 0; i < arr.length; i++) {                    
            if (arr[i].length) {                        
                fn(arr[i]);                    
            }else{                        
                newarr.push(arr[i]);                    
            }                
        }            
    }            
    fn(arr);                       
    return newarr;        
}        
Array.prototype.u = function () {//去重            
    var newarr = [];            
    var obj = {};            
    for (var i = 0; i < this.length; i++) {                
        if (!obj[this[i]]) {                   
            newarr.push(this[i]);                    
            obj[this[i]] = 1;                
        }            
    }            
    return newarr;        
}        
function compare (c1,c2) {//排序            
    return c1 -c2;        
}               
var arr = [2, -5, 6, [6, -5, [2, 5], [8, 10, [6, 8], -3], 2], 5]        
var a = [];        
a = f(arr);        
b = a.u();        
c = b.sort(compare);        
console.log(c);复制代码

var arr = [2, -5, 6, [6, -5, [2, 5], [8, 10, [6, 8], -3], 2], 5];        
function f (arr) {            
    var newarr = [];            
    function fn (arr) {                
        for (var i = 0; i < arr.length; i++) {                    
            if (arr[i].length) {                        
                fn(arr[i]);                    
            }else{                        
                newarr.push(arr[i]);                    
            }                
        }            
    }            
    fn(arr);            
    return newarr;        
}        
var x = f(arr);        
var newarr = [];        
for(var n = 0;n < x.length; n++) {           
    if (newarr.indexOf(x[n]) == -1) {               
        newarr.push(x[n]);           
    }        
}        
newarr.sort((a, b) => a - b)        
console.log(newarr)复制代码

两种方法其实大同小异，第一种方法看起来更高端一些。

三. 数组排序

1. sort排序法

（1）简单数组的简单排序

var arrSimple=new Array(1,8,7,6);
arrSimple.sort();
console.log(arrSimple.join()) ;复制代码

（2）简单数组的自定义排序

var arrSimple2=new Array(1,8,7,6);
arrSimple2.sort(function(a,b){    
    return a-b
});
console.log(arrSimple2.join())复制代码

解释：a,b表示数组中的任意两个元素，a-b输出从小到大排序，b-a输出从大到小排序。

（3）简单对象 List 自定义属性排序

var objectList = new Array();
function Persion(name,age){      
    this.name=name;      
    this.age=age;
}
objectList.push(new Persion('jack',20));
objectList.push(new Persion('tony',25));
objectList.push(new Persion('stone',26));
objectList.push(new Persion('mandy',23));
//按年龄从小到大排序
objectList.sort(function(a,b){      
    return a.age-b.age
});
for(var i=0;i<objectList.length;i++){      
    document.writeln('<br />age:'+objectList[i].age+' name:'+objectList[i].name);
}复制代码

（4）简单对象 List 对可编辑属性的排序

var objectList2 = new Array();        
function WorkMate(name,age){            
    this.name=name;            
    var _age=age;            
    this.age=function(){                
        if(!arguments){                    
            _age=arguments[0];
         }else{                   
            return _age;
         }                
    }                            
}        
objectList2.push(new WorkMate('jack',20));        
objectList2.push(new WorkMate('tony',25));        
objectList2.push(new WorkMate('stone',26));        
objectList2.push(new WorkMate('mandy',23));        
//按年龄从小到大排序        
objectList2.sort(function(a,b){            
    return a.age()-b.age();          
});        
for(var i=0;i<objectList2.length;i++){            
    document.writeln('<br />age:'+objectList2[i].age()+' name:'+objectList2[i].name);  
}复制代码

2. 冒泡排序法

解析：1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。

2.第一轮的时候最后一个元素应该是最大的一个。

3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较)（所以减 i ）。

var arr=[7,20,3,8,4,9,4,0,-4,1]        
function sort(elements){            
    for(var i=0;i<elements.length-1;i++){                
        for(var j=0;j<elements.length-i-1;j++){                    
            if(elements[j]>elements[j+1]){                        
                var swap=elements[j];                        
                elements[j]=elements[j+1];                        
                elements[j+1]=swap;                    
            }                
        }            
    }        
}         
console.log("before:"+arr)//before:[7,20,3,8,4,9,4,0,-4,1] 
sort(arr);        
console.log("after:"+arr) //after:-4,0,1,3,4,4,7,8,9,20复制代码

二维数组使用冒泡排序

方法1：

var arr=[["北京",80],["上海",50],["福州",10],["广州",50],["成都",70],["西安",100]];
var t;
for(var i=0;i<arr.length;i++){    
    for(var j=0;j<arr.length-1;j++){        
        if(arr[j][1]>arr[j+1][1]){            
            t=arr[j][1];            
            arr[j][1]=arr[j+1][1];            
            arr[j+1][1]=t;        
        }    
    }
}
console.log(arr);  
//["福州",10],["上海",50],["广州",50],["成都",70],["北京",80],["西安",100]复制代码

方法2：（选择排序法）

var arr=[["北京",80],["上海",50],["福州",10],["广州",50],["成都",70],["西安",100]];
for(var i=0;i<arr.length;i++){        
    for(var j=i+1;j<arr.length;j++){                
        if(arr[i][1]>arr[j][1]){                        
            var t=arr[j][1];                        
            arr[j][1]=arr[i][1];                        
            arr[i][1]=t;                
        }        
    }
}
console.log(arr);  复制代码

冒泡排序动图：

3. 选择排序法

相对于冒泡排序还有一种类似的方法就是选择排序，顾名思义就是选择性排序，什么意思呢？

这么来理解，假设在三伏天有一趟室内游泳课，教练说了先在露天场地等着，从你们当中先选取最大个先进去，然后再从剩余的人中选择最大个进去，依次类推。那么小个的就在想了，教练你TMD的脑子是不是被驴踢了。但是如果是冒泡排序那更有意思了，所有的人先排好队再进去，这样还好一点最起码每个人的心理能平衡一点。简单理解选择排序就是从一个未知数据空间，选取数据之最放到一个新的空间。

废话不多说，看例子：

var array = [1,4,-8,-3,6,12,9,8];        
function selectSort(arr){            
    for(var i=0;i<arr.length;i++){                
    //设置当前范围最小值和索引                
    var min = arr[i];             
    var minIndex = i;                
    //在该范围选出最小值                
        for(var j=i+1;j<arr.length;j++){                    
            if(min>arr[j]){                       
                min = arr[j];                       
                minIndex = j;                    
            }                
        }                
    //将最小值插入,并将原来位置的最小值删除                
    arr.splice(i,0,min);                
    arr.splice(minIndex+1,1);            
    }        
}        
selectSort(array);        
document.write(array);复制代码

（1）在未排序序列中找到最小（大）元素
（2）并存放到排序序列的起始位置
（3）然后，再从剩余未排序元素中继续寻找最小（大）元素
（4）然后放到已排序序列的末尾。
（5）以此类推

选择排序动图

4. 插入排序法

（1）从第一个元素开始，该元素可以认为已经被排序

（2）取出下一个元素，在已经排序的元素序列中从后向前扫描

（3）如果该元素（已排序）大于新元素，将该元素移到下一位置

（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

（5）将新元素插入到下一位置中

（6）重复步骤2

var array = [1,4,-8,-3,6,12,9,8];        
function insertSort(arr){
//假设第0元素是有序序列，第1元素之后是无序的序列。从第1元素开始依次将无序序列的元素插入到有序序列中      
    for(var i=1; i<arr.length;i++){
        if(arr[i]<arr[i-1]){    
            //取出无序序列中需要插入的第i个元素       
            var temp = arr[i];                    
            //定义有序中的最后一个位置                    
            var j = i-1;                    
            arr[i] = arr[j];                                     
            while(j>=0 && temp<arr[j]){ //比较大小，找到插入的位置
                arr[j+1] = arr[j];                        
                j--;                   
            };                                       
           arr[j+1] = temp; //插入             
       }            
    }        
}        
insertSort(array)       
 console.log(array);复制代码

插入排序动图

5. 希尔排序法

function shellSort(arr) {　　
    var len = arr.length, temp, gap = 1;　　
    console.time('希尔排序耗时:');　　
    while(gap < len/5) { //动态定义间隔序列　　　　
        gap =gap*5+1;　　
    }　　
    for (gap; gap > 0; gap = Math.floor(gap/5)) {　　　　
        for (var i = gap; i < len; i++) {　　　　　　
            temp = arr[i];　　　　　　
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {　　　　　　　　
                arr[j+gap] = arr[j];　　　　　　
            }　　　　　　
            arr[j+gap] = temp;　　　　
        }　　
    }　　
    console.timeEnd('希尔排序耗时:');　　
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]；复制代码

当读到while循环时，我类个去，什么鬼？什么意思？再往下读，好了，放弃吧！看起来云里雾里，变量附来附去，什么意思？

抽象看不明白那就实例化，以arr为例代进去一看究竟，len/5 以五步为增量，这好像是说的通，但是gap = gap *5 +1 ；这是什么鬼？

别着急慢慢读，len = 15 ,gap = 6 ;while循环结束。再往下读，var i = gap ；也就是说从i = 6开始循环一直到数组末尾，然后从i=6开始记录元素，而对于下标为 j 的for循环，则是从0开始，然后以步长为6开始比较，接下来就会发现一个问题，j-=gap ？又是什么鬼？ j=0,j-=gap ,那 j 不就是负的了么？编者这么写是有他的理由的，对，在下标为6之前的元素之循环了一次，那下边如果超过6呢，所以小编觉得这个地方也算是个亮点吧！

还没结束，这层内层循环结束了，跳了出来，gap = Math.floor(gap/5) 又是什么玩意？只是常规的思想局限了创新，这个不就是与while循环的gap = gap *5+1 ；与之相应么？这么做有什么好处呢，也就是说无论数据有多大，最终肯定会走到每隔6步为已增量的循环中，这就是希尔排序的亮点所在，而且前面定义的gap=1；还有gap = gap*5+1 ；这个1不是随便定义的，因为最终回归到的就是增量为1的循环当中！

6. 归并排序法

归并排序其实可以类比二分法，二分法其实就是二等分的意思，简而言之就是不断和新序列的中间值进行比较。归并排序似乎有异曲同工之妙，什么意思呢，就是将一个原始序对等分为两部分，然后不断地对等分新的序列，直至序列的长度为1或者2，那么想，如果一个序列为1，那就没有比较的意义了，它本身就是之最，如果是两个呢，那直接比较不就完了，把比较之后的值推送到一个新的数组。就这样不断地细分，不断的产生子序列，然后把穿产生的新序列作为新的父序列，然后同等级的父序列再比较产生新的祖序列，依次类推。

2019面试 JS排序和数组去重有哪些方法?

正文