你的位置:首页 > Java教程

[Java教程]JS快速排序和去重


JS的快速排序和JS去重在面试的时候问的挺多的.下面是我对快速排序的理解,和快速排序,去重的代码.

1.什么是快速排序?

      第一步: 快速排序就是去个中间值,把比中间值大的放在右边设为arrLeft,比中间值小的放在右边设为arrRight

      第二步: 对arrLeft进行第一步,对arrRight进行第一步.(明显是一个递归嘛,当数组的长度小于2的时候结束)

      第三步: 合并arrLeft,中间值,arrRight

     

 1  quickSort = function(arr){ 2     if(arr.length < 2){ 3       return arr; 4     } 5     var tmp  = arr.splice(Math.floor(arr.length/2), 1)[0], 6       arrLeft = [], 7       arrRight = []; 8      9     for(var i = 0; i < arr.length; i++){10       if(arr[i] >= tmp){11         arrRight.push(arr[i]);12       }else{13         arrLeft.push(arr[i]);14       }15     }16     return arguments.callee(arrLeft).concat(tmp,arguments.callee(arrRight));18 19  }

2.JS的去重?

      大家第一个想到的应该是,循环一次数组,每取到一个值就与后面的比较,如果没有相同的就放入一个新数组里面,这样就去重了

 

第一种
var unique1 = function(arr){  var newArr = [];  while(arr.length){    var value = arr.shift();    for(var i = 0, len = arr.length; i<len; i++){      if(value == arr[i]){        break;      }    }    if(i == len){      newArr.push(value);    }  }  return newArr;}

   

      但是这样循环了二次,效率不好.下面提供的较好,声明一个对象,数组的值作为对象的属性并赋值为一,然后判断这个对象属性是否存在就行了

 

 第二种
 1 var unique2 = function(arr){ 2   var arr = []; 3   var obj = {}; 4   for(var i = 0, len = a.length; i < len; i++){ 5      if(!obj[a[i]]){ 6       obj[a[i]] = 1; 7       arr.push(a[i]); 8       } 9   }10   console.log(obj)11   return arr;12 };

 

       还有一种就是排序并去重 ,这种就更加容易了.判断前面一个值是不是等于后面一个值如果相等,往后移动一位就行了

 

 第三种

1 var unique3 = function(arr){ 2 var newArr = []; 3 for(var i = 0, len = arr.length; i <len; i++){ 4 if(arr[i] !== arr[i+1]){ 5 newArr.push(arr[i]); 6 } 7 if(i == len){ 8 newArr.push(arr[i]); 9 }10 }11 return newArr;12 }