JS快速排序和去重_JS实现数组去重排序
2018-08-21 13:18:27  By: dwtedx

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

1.什么是快速排序?

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

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

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

quickSort = function(arr){
    if(arr.length < 2){
      return arr;
    }
    var tmp   = arr.splice(Math.floor(arr.length/2), 1)[0],
      arrLeft  = [],
      arrRight = [];

    for(var i = 0; i < arr.length; i  ){
      if(arr[i] >= tmp){
          arrRight.push(arr[i]);
      }else{
          arrLeft.push(arr[i]);
      }
    }
    return arguments.callee(arrLeft).concat(tmp,arguments.callee(arrRight));

}


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;
}


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

//第二种
var unique2 = function(arr){
    var arr = [];
    var obj = {};
    for(var i = 0, len = a.length; i < len; i  ){
           if(!obj[a[i]]){
            obj[a[i]] = 1;
            arr.push(a[i]);
           }
    }
    console.log(obj)
    return arr;
};

 

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

//第三种
var unique3 = function(arr){
    var newArr = [];
    for(var i = 0, len = arr.length; i <len; i  ){
        if(arr[i] !== arr[i 1]){
            newArr.push(arr[i]);
        }
        if(i == len){
            newArr.push(arr[i]);
        }
    }
    return newArr;
}


若资源对你有帮助、浏览后有很大收获、不妨小额打赏我一下、你的鼓励是维持我不断写博客最大动力

想获取DD博客最新代码、你可以扫描下方的二维码、关注DD博客微信公众号(ddblogs)

或者你也可以关注我的新浪微博、了解DD博客的最新动态:DD博客官方微博(dwtedx的微博)

如对资源有任何疑问或觉得仍然有很大的改善空间、可以对该博文进行评论、希望不吝赐教

为保证及时回复、可以使用博客留言板给我留言: DD博客留言板(dwtedx的留言板)

感谢你的访问、祝你生活愉快、工作顺心、欢迎常来逛逛


快速评论


技术评论

  • 该技术还没有评论、赶快抢沙发吧...
DD记账
top
+