JavaScript数组排序与去重算法详解：从基础到分治策略

JavaScript数组排序与去重算法详解：从基础到分治策略

在JavaScript中，实现数组排序通常可以直接利用内置的sort方法，这种方式相对简便。

一、排序

一、排序

简单实现数组排序

var arr = [];
for(var i=0;i<20;i++){
arr.push(Math.floor(Math.random()*100))
}  
arr.sort(function(a,b){
return a>b?1:-1;
})  
alert(arr)

需要注意的是，不能简单地直接使用sort方法。因为默认情况下，sort方法会按照ASCII字母顺序进行排序，而不是我们期望的数字大小顺序。

sort() 方法可以接受一个函数作为参数，该函数包含两个参数，分别代表每次排序比较时的两个数组元素。

在sort()排序过程中，每次比较两个数组项时都会执行这个参数函数，并将这两个比较的数组项作为参数传递给该函数。当函数返回值为1时，交换两个数组项的顺序；否则不交换。

算法的数组排序

算法的数组排序

var arr = [];
for(var i=0;i<20;i++){
arr.push(Math.floor(Math.random()*100))
}  
//生成一个无序的arr数组
function sort(arr,start,end){
//数组长度为1
if(start == end ){
return [arr[start]]
}else if(start == end-1){
//数组长度为2，根据数值大小 来排序
if(arr[start]>arr[end]){
return [arr[end],arr[start]]
}else{
return [arr[start],arr[end]]
        }  
    }  
// 数组长度一半
var l = Math.floor((start+end)/2);
//左边数组
var arrLeft = sort(arr, start,l);
//右边数组
var arrRight = sort(arr,l+1,end);
//返回结果
var result = [];
//分割成两部分 左右两个数组 只比对数组中的第一个数，那个数值小就把谁放到结果里面，并把小的数值删除掉，固采用数组中的shift方法。一旦出现左边数组或右边数组，没有数据的时候
//result数组就与还有数据的数组合并 采用 concat,并返回结果
while(arrLeft.length>0 || arrRight.length>0){
if(arrLeft.length==0){
result = result.concat(arrRight);
break;
}else if(arrRight.length==0){
result = result.concat(arrLeft);
break;
        }  
if(arrLeft[0]<arrRight[0]){
result.push(arrLeft.shift())
}else{
result.push(arrRight.shift());
        }  
    }  
return result;
}  
var arrSort = sort(arr,0,arr.length-1);//参数 数组，开始位置，结束位置
document.write(arr+'<br/>'+arrSort);

讲解：数组排序主要是采用将数组一拆为二，直到不能为之，最后只能是拆掉数组里面只能是一个或者是两个，因为数组的长度有奇数偶数之分，拆到最后 数组里面只有一个或者两个之后 开始排序并返回结果，并将这些结果在一一比对 进行合并。这个方法 可能大家觉得 为什么要这么复杂，一直采用第一种不行吗，其实当然可以啦，但是这个世界上还有性能这个词汇，当数据之后几个 几十个 几个百 ，大家的算出的结果时间是没有什么区别的 ，如果当数据庞大的几亿 几十亿 我们还有这种自信用第一种方法吗，其实js的算法就是分而治之，将很多问题划分成小的来解决。

二、数组去掉重复

二、数组去掉重复

简单方法去掉重复：先声明一个空的数组，将重复的数组 for 循环插入，重复的跳过 不重复的插入

var arr = [];
for(var i=0;i<20;i++){
arr.push(parseInt(Math.random()*10));
}  
Array.prototype.indexOf = function(n){
for(var i=0;i<this.length;i++){
if(this[i] == n){
return i;
        }  
    }  
return -1;
}  
function removeDup(arr){
var result = [];
for(var i=0;i<arr.length;i++){
if(result.indexOf(arr[i]) == -1){
result.push(arr[i]);
        }  
    }  
return result;
}  
var arr2 = removeDup(arr)
document.write(arr+'<br/>'+arr2)

算法数组去掉重复

算法数组去掉重复

var arr = [];
for(var i=0;i<20;i++){
arr.push(parseInt(Math.random()*10));
}  
Array.prototype.indexOf = function(n){
for(var i=0;i<this.length;i++){
if(this[i] == n){
return i;
        }  
    }  
return -1;
}  
function removeDup(arr,s,e){
if(s==e){
//分割就剩下一个
return [arr[s]]
}else if(s==e-1){
//为了优化 剩下两个就不用分割啦
if(arr[s]==arr[e]){
return [arr[s]]
}else{
return [arr[s],arr[e]];
        }  
    }  
//数组平分成两段，
var l = Math.floor((s+e)/2);
//左边
var arrL = removeDup(arr,s,l);
//右边
var arrR = removeDup(arr,l+1,e);
//结果 先把左边的复制进去
var result = arrL;
//循环 将不重复的数据插入到结果里面
for(var i=0;i<arrR.length;i++){
if(result.indexOf(arrR[i])== -1 ) result.push(arrR[i])
    }  
return result; //返回结果
}  
var arrDup = removeDup(arr, 0, arr.length-1);
document.write(arr+'<br/>'+arrDup);

将重复的数组 切割，拆分到最后只剩下一个数据或或者两个数组，将左边的数据放到结果里面，右边重复的跳过 不重复插入，直到循环完，返回结果就可以