快速排序法
快速排序是一种非常经典高效的排序算法，时间复杂度为O(nlog2n)，2为底数，其内部循环架构效率很高，主要思想为：
- 在数据集之中，选择一个元素作为"基准"（pivot）；
- 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边；
- 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止，从小到大拼接所有子集。
代码如下：
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));
};
二分查找法
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。其时间复杂度为O(log2n)，2为底数。因此，折半查找方法适用于不经常变动而查找频繁的有序列表，主要思想为：
- 将数据集按升序排列；
- 将数据集中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将数据集分成前、后两个子数据集，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子数据集，否则进一步查找后一子数据集。
- 重复以上过程，直到找到满足条件的记录，此时查找成功；或直到子数据集不存在为止，此时查找不成功。
代码如下
function halfSearch(data, item) {
var h = data.length - 1;
var l = 0;
var m = Math.floor((h + l) / 2);
while(h >= l) {
if(data[m] == item) {
return m;
} else {
if(data[m] > item) {
h = m - 1;
} else {
l = m + 1;
}
}
m = Math.floor((h + l) / 2);
}
return false;
}
浅复制和深复制
对象浅复制指利用in枚举方法把对象的每个属性值赋予一个新的空对象，实现对象复制。但是旧对象属性值若是对象，新对象复制的只是指针，所以新旧对象这个属性值依然共用同一个对象。
对象深复制是指利用in和递归方法，解决浅复制中属性值共用相同对象的问题，实现完全复制一个没有关联的新对象。
代码如下
//浅复制
function shallowCopy(obj) {
var newObj;
if (obj instanceof Array) {
newObj = [];
} else {
newObj = {};
}
for (var key in obj) {
newObj[key] = obj[key];
}
return newObj;
}
//深复制
function deepCopy(obj) {
var newObj;
if (obj instanceof Array) {
newObj = [];
} else {
newObj = {};
}
for (var key in obj) {
if (obj[key] instanceof Object) {
newObj[key] = deepCopy(obj[key]);
} else {
newObj[key] = obj[key];
}
}
return newObj;
}
参考文献：http://www.jb51.net/article/91906.htm
数组去重
代码如下
function removeDuplicatedItem(arr) {
var newArr = [];
for (var index = 0; index < arr.length; index++) {
if (newArr.indexOf(arr[index]) === -1) {
newArr.push(arr[index]);
}
}
return newArr;
}
计算字符串每个字符的个数
function countChar(str) {
var arr = [];
for (var index = 0; index < str.length; index++) {
var element = str[index];
if (arr.indexOf(element) === -1) {
arr.push(element);
}
}
var result = [];
for (var index = 0; index < arr.length; index++) {
var element = arr[index];
var i = 0;
for (var b = 0; b < str.length; b++) {
var char = str[b];
if (char === element) {
i++;
}
}
var tempArr = [element, i];
result.push(tempArr);
}
return result
}