最近关注前端性能一方面比较多，发现算法的性能改变也是其中一个很大的改善点，特别在数据量很大的情况下，在这里总结了几个前端经常都用得上的算法。
冒泡排序
思想: 比较相邻的两个数，如果后面的比前面的小，把小的放在前面。一轮过后，会有这一轮最小（大）的值去到应到的位置。
时间复杂度: O(n2)
code：优化点:如果数组已经是有序了，就没必要再比较了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23var arr=[5,3,2,4,1,0];
function bubbleSort(arr){
var flag = false;
//定义一个变量为false，未交换位置;
for(var i=0;i<arr.length-1;i++){
for(var j=0;j<arr.length-1;j++){
if(arr[j+1]<arr[j]){
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
flag = true; //true，已交换位置
}
}
if(flag){
flag = false; //如果交换了位置，将flag重新设为false
}else{
break; //如果未交换，则跳出循环
}
}
return arr;
}
console.log(bubbleSort(arr)); //0,1,2,3,4,5
设置一个中断标志位，在条件测试中如果发生了交换就将中断位屏蔽，然后在外层循环中检查中断位，如果中断位没有被屏蔽，将结束循环。每次开始内层循环之前重置中断位。这样就可以在已经是正序排列时不继续进行循环，达到最优的复杂度.
选择排序
思想： 先从原始数组中选择一个最小的数据，和第一个位置1的数据交换。再从剩下的n-1个数据中选择次小的数据，将其和第二个位置的数据交换。不断重复，知道最后两个数据完成交换。可以很清楚的发现，选择排序是固定位置，找元素。
时间复杂度： O(n2)
code1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23var arr=[5,3,2,4,1,0];
function selectionSort(array){
var min,temp;
for(var i=0; i<array.length-1; i++){
min=i;
for(var j=i+1; j<array.length; j++){
if(array[j]<array[min]){
min=j;
}
}
swap(array,min,i);
}
return array;
}//选择排序
function swap(array,i,j){
var temp =array[i];
array[i]=array[j];
array[j]=temp;
}//两个数字交换
console.log(selectionSort(arr)); //0,1,2,3,4,5
快速排序
思想：
- 在数据集之中，选择一个元素作为”基准”（pivot）。
- 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。
- 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
eg:
选6为基准
1 | ------------------------------------------- |
时间复杂度 :平均O(nlgn)，最坏O(n2)
code:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16var quickSort = function(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));
};
console.log(quickSort(arr));
归并排序
思想： 把一个数组分为两个数组，左边排好序，右边排好序，然后合并到一起排序
归并排序是分治法的典型实例，指的是将两个已经排序的序列合并成一个序列的操作
**时间复杂度： O(nlogn)
code：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34var arr=[-11,17,12,19,0,-222];
function mergeSort(arr,s,e){
if(s>e){
//起始位置大于终点位置，返回空数组
return [];
}else if(s==e){
return [arr[s]];
//起始位置等于终点位置，说明数组里只有一个数字，返回只含一个数字的数组
}
var mIndex = Math.floor((s+e)/2); //中间位置的Index
var arrL = mergeSort(arr,s,mIndex); //将左边的数组排序
var arrR = mergeSort(arr,mIndex+1,e); //将右边的数组排序
var resultArr = []; //结果数组
while(arrL.length>0 || arrR.length>0){ //当左右两个数组都不为空时
if(arrL[0]<arrR[0]){
resultArr.push(arrL.shift());
}else{
resultArr.push(arrR.shift());
}
if(arrL.length==0){ //当左边的数组为空时
resultArr = resultArr.concat(arrR);
break;
}else if(arrR.length==0){
resultArr = resultArr.concat(arrL);
break;
}
}
return resultArr;
}
console.log(mergeSort(arr,0,arr.length-1))
