2919面试 JS十大排序算法与14种去重算法

第一部分：数组排序

图片名词解释：

n: 数据规模

k:“桶”的个数

In-place: 占用常数内存，不占用额外内存

Out-place: 占用额外内存

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())复制代码

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);
}复制代码

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，那就没有比较的意义了，它本身就是之最，如果是两个呢，那直接比较不就完了，把比较之后的值推送到一个新的数组。就这样不断地细分，不断的产生子序列，然后把穿产生的新序列作为新的父序列，然后同等级的父序列再比较产生新的祖序列，依次类推。

有点抽象了，那就具体化，比如现在有个十万人的司令部，习大大是首长，习大大跟司令说了，把所有的人按年龄排序，司令想了，让我一个人也忙活不过来啊，这怎么办，然后就把任务下达给军长，军长下达给师长，依次类推，排长再把一个排分成两个小队，小队再分成两个小组，最后分成两个人一组或一人一组，接下来就是组员之间进行比较，完了小队与小队比较，排与排之间比较，依次类推，最后军团和军团比较，形成最后的序列。

废话不多说，看代码：

function mergeSort(arr) { //采用自上而下的递归方法　　var len = arr.length;　　if(len < 2) {　　　　return arr;　　}　　var middle = Math.floor(len / 2),　　left = arr.slice(0, middle),　　right = arr.slice(middle);　　return merge(mergeSort(left), mergeSort(right));} function merge(left, right){　　var result = [];　　console.time('归并排序耗时');　　while (left.length && right.length) {　　　　if (left[0] <= right[0]) {　　　　　　result.push(left.shift());　　　　} else {　　　　　　result.push(right.shift());　　　　}　　} 　　while (left.length){　　　　result.push(left.shift());　　}　　while (right.length){　　　　result.push(right.shift());　　}　　console.timeEnd('归并排序耗时');　　return result;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(mergeSort(arr));复制代码

7. 快速排序法

对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。

var array = [1,4,-8,-3,6,12,9,8];
function quickSort(arr){
//如果数组长度小于等于1，则返回数组本身    
    if(arr.length<=1){        
        return arr;    
    }    
    var index = Math.floor(arr.length/2);  //定义中间值的索引    
    var temp = arr.splice(index,1); //取到中间值 
    //定义左右部分数组    
    var left = [];    
    var right = [];    
    for(var i=0;i<arr.length;i++){     
        //如果元素比中间值小，那么放在左边，否则放右边        
        if(arr[i]<temp){           
            left.push(arr[i]);        
        }else{            
            right.push(arr[i]);        
        }    
    }    
    return quickSort(left).concat(temp,quickSort(right));
}
console.log(quickSort(array));复制代码

Math.floor(x)方法是向下取整，返回小于或等于x的最接近的整数。

splice(index,num,item)方法是向数组中添加项目，或是从数组中删除项目，并返回被删除的项目。

• index是整数，被操作项目所在的位置（必须）
• num是整数，要删除的项目的数量，如果为0，表示不删除（必须）
• item是向数组中添加的新项目，可以是多个（可选）

push()方法是向数组末尾添加一个或多个新项目并返回新数组的长度

concat()方法连接两个或多个数组，不会改变原有数组，返回一个新数组

快速排序动图

8. 堆排序

这种排序方式呢，理论性太强，看动图的时候满脸写着懵逼，多看几遍似乎明白了编者的意图，但是要把这种理论的概念写成代码却不容易，且看代码：

function heapSort(array) {        　　
    console.time('堆排序耗时');        　　
    //建堆        　　
    var heapSize = array.length, temp;        　　
    for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {　　        　　　　
        heapify(array, i, heapSize);        　　
    }        　　
    //堆排序        　　
    for (var j = heapSize - 1; j >= 1; j--) {        　　　　
        temp = array[0];        　　　　
        array[0] = array[j];        　　　　
        array[j] = temp;        　　　　
        heapify(array, 0, --heapSize);        　　
    }        　　
    console.timeEnd('堆排序耗时');        　　
    return array;        
}        
function heapify(arr, x, len) {        　　
    var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;        　　
    if (l < len && arr[l] > arr[largest]) {        　　　　
        largest = l;        　　
    }        　　
    if (r < len && arr[r] > arr[largest]) {        　　　　
        largest = r;        　　
    }        　　
    if (largest != x) {        　　　　
        temp = arr[x];        　　　　
        arr[x] = arr[largest];        　　　　
        arr[largest] = temp;        　　　　
        heapify(arr, largest, len);        　　
    }        
}        
var arr = [-26, 54, 25, 7, -21, 24, 68, 29, 16, 41, 87];        
console.log(heapSort(arr));复制代码

9. 计数排序法

计数排序就是遍历数组记录数组下的元素出现过多次，然后把这个元素找个位置先安置下来，简单点说就是以原数组每个元素的值作为新数组的下标，而对应小标的新数组元素的值作为出现的次数，相当于是通过下标进行排序。

function countingSort(array) {        　　
    var len = array.length, B = [], C = [], min = max = array[0];        　　
    console.time('计数排序耗时');        　　
    for (var i = 0; i < len; i++) {        　　　　
        min = min <= array[i] ? min : array[i];        　　　　
        max = max >= array[i] ? max : array[i];        　　　　
        C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;        　　
    }        　　
    // 计算排序后的元素下标        　　
    for (var j = min; j < max; j++) {        　　　　
        C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);        　　
    }        　　
    for (var k = len - 1; k >= 0; k--) {        　　　　
        B[C[array[k]] - 1] = array[k];        　　　　
        C[array[k]]--;        　　
    }        　　
    console.timeEnd('计数排序耗时');        　　
    return B;        
}        
var arr = [-26, 54, 25, 7, -21, 24, 68, 29, 16, 41, 87];        
console.log(countingSort(arr)); 复制代码

10. 桶排序

一看到这个名字就会觉得奇特，几个意思，我排序还要再准备几个桶不成？还真别说，想用桶排序还得真准备几个桶，但是此桶非彼桶，这个桶是用来装数据用的。其实桶排序和计数排序还有点类似，计数排序是找一个空数组把值作为下标找到其位置，再把出现的次数给存起来，这似乎看似很完美，但也有局限性，不用小编说相信读者也能明白，既然计数是把原数组的值当做下标来看待，那么该值必然是整数，那假如出现小数怎么办？这时候就出现了一种通用版的计数排序——桶排序。

我得桶排序可以这么理解，它是以步长为分隔，将最相近数据分隔在一起，然后再在一个桶里排序。好了，现在有个概念，步长是什么玩意？这么来说吧，比如在知道十位的情况下48和36有比较的必要吗？显然没有，十位就把你干下去了，还比什么？那在这里可以简单的把步长理解为10，桶排序就是这样，先把同一级别的分到一组，由同一级别的元素进行排序。

代码实现：

@param array 数组

@param num 桶的数量

function bucketSort(array, num) {        　　
    if (array.length <= 1) {        　　　　
        return array;        　　
    }        　　
    var len = array.length, buckets = [], result = [], min = max = array[0], space, n = 0; 　
    var index = Math.floor(len / num) ;        　　
    while(index<2){        　　　　
        num--;        　　　　
        index = Math.floor(len / num) ;        　　
    }        　　
    console.time('桶排序耗时');        　　
    for (var i = 1; i < len; i++) {        　　　　
        min = min <= array[i] ? min : array[i];        　　　　
        max = max >= array[i] ? max : array[i];        　　
    }        　　
    space = (max - min + 1) / num;  //步长        　　
    for (var j = 0; j < len; j++) {        　　　　
        var index = Math.floor((array[j] - min) / space);        　　　　
        if (buckets[index]) { // 非空桶，插入排序        　　　　　　
            var k = buckets[index].length - 1;        　　　　　　
            while (k >= 0 && buckets[index][k] > array[j]) {        　　　　　　　　
                buckets[index][k + 1] = buckets[index][k];        　　　　　　　　
                k--;        　　　　　　
            }        　　　　　　
            buckets[index][k + 1] = array[j];        　　　　
        } else { //空桶，初始化        　　　　　　
            buckets[index] = [];        　　　　　　
            buckets[index].push(array[j]);        　　　　
        }        　　
    }        　　
    while (n < num) {        　　　　
        result = result.concat(buckets[n]);        　　　　
            n++;        　　
    }        　　
    console.timeEnd('桶排序耗时');        　　
    return result;        
}        
var arr = [-26, 54, 25, 7, -21, 24, 68, 29, 16, 41, 87];        
console.log(bucketSort(arr,4));复制代码

但是这边有个坑点，就是桶的数量不能过多，也就说说至少两个桶！为什么？你试下就知道了！

附图理解：

第二部分：数组去重

数组去重，一般都是在面试的时候才会碰到，一般是要求手写数组去重方法的代码。如果是被提问到，数组去重的方法有哪些？你能答出其中的10种，面试官很有可能对你刮目相看。

在真实的项目中碰到的数组去重，一般都是后台去处理，很少让前端处理数组去重。虽然日常项目用到的概率比较低，但还是需要了解一下，以防面试的时候可能回被问到。

一、建立一个空的数组

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());复制代码

二、用 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);复制代码

三、利用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", {}, {}]复制代码

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

四、利用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直接消失了复制代码

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

五、利用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进数组。

六、利用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()排序方法，然后根据排序后的结果进行遍历及相邻元素比对。

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

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和{}去重复制代码

八、利用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", {…}, {…}]     
//{}没有去重复制代码

九、利用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 判断是否存在对象属性

十、利用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", {…}, {…}]复制代码

十一、利用递归去重

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]复制代码

十二、利用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值，所以最终得到的就是去重后的结果。

十三、利用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", {…}, {…}]复制代码

十四、[...new Set(arr)]

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