logo头像

求知若渴,虚心若愚

前端常见排序算法

前端开发中常见的前端算法题,包含冒泡排序,快速排序,二分查找法等等

1. 冒牌排序

1.1 排序思路

遍历数组,每次遍历就将最大(或最小)值推至最前。越往后遍历查询次数越少, 跟插入排序刚好相反

1.2 实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 冒泡排序 每次将最小元素推至最前
var arr = [44,65,3,774,334,987,434,12,11,44]
function maopao(arr) {

for(var i = 0 ; i < arr.length;i++){
var temp
for(var j = 0 ; j < arr.length -1 - i ; j++){
if(arr[j]>=arr[j+1]){
temp = arr[j+1]
arr[j+1]=arr[j]
arr[j]=temp
}
}

}
return arr
}

2. 快速排序

2.1 实现思路

  • 在数据集之中,选择一个元素作为”基准”(pivot)。
  • 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。
  • 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止

2.2 实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var 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));
};
支付宝打赏 微信打赏

赞赏是对我们的肯定!