javascript 从去重到排序的考量

写这篇文章的原因是因为在某个简单的问题上翻船,往往高手和新手的区别就在于看似平常的地方,一直以来都在思考高手和新手的本质区别,高手绝非工作经验和工作时间的堆积造就的,10年工作经验的人也许是1年工作经验用了十年也不一定。

这里有一道题目,是这样:数组去重、并按倒数第二个字母排序

这个问题实在是非常简单
去重:定义一个新的数组,取出原数组的元素,依次放入新的数组,放入之前需要检查是否在新的数组已经存在即可。
排序:使用数组的sort()方法,javascript 默认使用冒泡排序,只需要传入2个元素的比较结果即可,按照题目,只需要取出字母,然后比较即可。
于是得到代码:

function uniqe(arr){
var tmp = {};
var result = [];
for(var i = 0,len = arr.length;i < len;i ++){
    var item = arr[i];
    if(item in tmp){
        continue;
    }
    result.push(item);
}
return result.sort(function(a,b){
    return a.charCodeAt(a.length-2) - b.charCodeAt(b.length-2);
});

}

var arr =['hello','world','nodejs','javascript',
'html','world','css','flash','adobe','java','hello'];
uniqe(arr)

那么我们把这个问题继续简化!!数字数组去重、并排序。
看这个问题是否更加简单?但是等等,这种基础函数,一般都需要承载丰富的业务逻辑,被大量引用,也许是在循环等复杂的逻辑中,因此要求足够健壮、高效。我们不仅需要检查输入还需要选择更好算法,解决这个问题的思路应该是:step1 排序 setp2 查找 step3 去重

快速排序算法

function quickSort(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);

  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
return .quickSort(left).concat([pivot], .quickSort(right));
}

二分法查找

function binarySearch(items,value){
var startIndex = 0, 
stopIndex = items.length - 1, 
middle = Math.floor((stopIndex + startIndex)/2); 
while(items[middle] != value && startIndex < stopIndex){ 
    if (value < items[middle]){ 
        stopIndex = middle - 1; 
    } else if (value > items[middle]){ 
        startIndex = middle + 1; 
    } 
    middle = Math.floor((stopIndex + startIndex)/2); 
} 
return (items[middle] != value) ? -1 : middle; 

}

去重

function distinct(arr){
arr = this.quickSort(arr);

  for (var i = 0; i < arr.length; i++){
var cell = arr.pop();
if (this.binarySearch(arr,cell) == -1) {
arr.push(cell);
};
  }
return arr;
}

但是到了这里绝对还没完!
高质量的代码还需要测试,我们引入Qunit,但是我们需要产生模拟数据,我们可以使用Mock.js