常用算法

前言

算法的重要性不必我说大家都知道吧,就是程序员的内功啊,然而大多数时候我们并不是很重视这个问题,直到面试的时候一个简单的快排都没法写出来才知道自己是有多窘迫,最终草草结束面试,与心仪的工作失之交臂。既然无法改变过去,那从现在开始抓紧时间学一下算法吧(起码基本的总得会吧)。

二分查法

给你1到100的有顺序的数,让你随便找一个数你得找多少次?正常情况,我们会从头数,一直数到要找的数,很显然这种方法很低效,有没有更为高效的方法?这里我介绍一种二分法。

什么是二分法

何为二分法,言简意赅,我们就是每一次取最大和最小值的中间值与要找的数进行比较,然后确定要查找的数的范围在那一边(比如值比中间数小,则要查找的数在左边范围,反之亦然),然后在指定范围内取中间值继续比较,一直找到要找的数(或者找不到)。

二分法实现

下面用代码实现二分法(亲测)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 返回元素所在索引
function dichotomization(array, item){
let midIndex;
let minIndex = 0;
let maxIndex = array&&(array.length-1);
if(!array||array.length == 0){
return;
}
midIndex = parseInt((minIndex+maxIndex)/2);
while(minIndex < maxIndex && array[midIndex] != item){
if(array[midIndex] < item){
minIndex = midIndex+1;
}else if(array[midIndex] > item) {
maxIndex = midIndex-1;
}
midIndex = parseInt((minIndex+maxIndex)/2);
}
if(array[midIndex] !== item){
console.log('没找到');
return ;
}
return midIndex;
}

排序

选择排序

什么是选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

代码实现

为了简化过程,我们份两步,先找出最小(大)的值,然后循环遍历找出每一次未排序部分的最小(大)的值。下面我们展示一个从小到大的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function sortSmall(array){
let newArr = [];
// 第一步
function findSmall(arr){
var index = 0;
for(let i = 0; i < arr.length; i++){
if(arr[index] > arr[i]){
index = i;
}
}
return index;
}
// 第二步
while(array.length != 0){
// splice返回的是数组
newArr.push(...array.splice(findSmall(array),1))
}
return newArr;
}

优缺点分析

优点:算法过程简单明了,容易实现。
缺点:时间复杂度为(n^2),运算速度相对较慢.

坚持原创技术分享,您的支持将鼓励我继续创作!