Appearance
基础算法
阶乘
javascript
/*
阶乘：
代表着所有小于或等于n的整数的乘积，数学上通常简写成 n!
*/
// 循环写法
function factorial1(num) {
var result = 1;
for (var i = 1; i <= num; i++) {
result *= i;
}
return result;
}
// 递归写法
function factorial2(n) {
if (n <= 1) {
return 1;
} else {
return n ### factorial2(n - 1);
}
}
// 更多资料
// https://segmentfault.com/q/1010000000672936
// https://blog.csdn.net/qq_37120738/article/details/79982652
// https://www.jianshu.com/p/bd73e0475a75斐波那契数
javascript
/*
斐波那契数：
斐波那契数列指的是这样一个数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...每一项都等于前两项之和
*/
// 迭代写法
function fibonacci1(n) {
var res1 = 1;
var res2 = 1;
var sum = res2;
for (var i = 2; i < n; i++) {
sum = res1 + res2;
res1 = res2;
res2 = sum;
}
return sum;
}
// 递归写法，参数n变大时，会出现浏览器假死现象
function fibonacci2(n) {
if (n <= 2) {
return 1;
} else {
return fibonacci2(n - 1) + fibonacci2(n - 2);
}
}
// 尾调用优化
function fibonacci3(n, res1 = 1, res2 = 1) {
if (n <= 2) {
return res2;
} else {
return fibonacci3(n - 1, res2, res1 + res2);
}
}
// 闭包写法，实现记忆功能，避免了重复计算，提高性能
const fibonacci4 = function() {
var mem = [0, 1];
var f = function (n) {
var res = mem[n];
if (typeof res !== 'number') {
mem[n] = f(n - 1) + f(n - 2);
res = mem[n];
}
return res;
}
return f;
}();
// 更多资料
// https://blog.csdn.net/qq_39300332/article/details/80000837
// https://www.cnblogs.com/iriszhang/p/6093175.html
// https://segmentfault.com/a/1190000018473729素数检测
javascript
/*
素数：
除了1和它本身以外不能被其它数整除的数，并且0和1不是素数
*/
// 判断一个数是不是素数
function isPrinme(n) {
if (n == 0 || n == 1) {
return false;
}
if (n == 2) {
return true;
}
for (var i = 2; i < Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// 输出n内的所有素数
function prinmeN(n) {
var flag = 0;
var result = [];
if (n == 0 || n == 1) {
result = [];
} else if (n == 2) {
result = [2];
} else if (n == 3 || n == 4) {
result = [2, 3]
} else {
result.push(2, 3);
for (var i = 5; i <= n; i++) {
for (var j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
flag = 1;
break;
} else {
flag = 0;
}
}
if (flag == 0) {
result.push(i);
}
}
}
return result;
}
// 更多资料
// https://www.cnblogs.com/lmjZone/p/9593063.html
// https://segmentfault.com/q/1010000008417183
// https://blog.csdn.net/yeyue1992/article/details/81348722最大公约数算法(GCD)
javascript
/*
最大公约数：
几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数
*/
// 普通循环版
function gcd(a, b) {
var min = Math.min(a, b);
for (var i = min; i > 0; i--) {
if (a % i == 0 && b % i == 0) {
return i;
}
}
}
// 简洁递归版
function gcd2(a, b) {
return b != 0 ? gcd2(b, a % b) : a;
}
// 更多资料
// https://www.cnblogs.com/zhao12354/p/5721542.html
// https://cobain-li.iteye.com/blog/2296959
// https://segmentfault.com/q/1010000019130268/a-1020000019131550最小公倍数 (LCM)
javascript
/*
最小公倍数：
两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数
*/
// 普通轮询
function lcm(a, b) {
var max = Math.max(a, b);
for (var i = max; i <= a ### b; i++) {
if (i % a == 0 && i % b == 0) {
return i;
}
}
}
// 更多资料
// https://www.cnblogs.com/zhao12354/p/5721542.html
// https://my.oschina.net/flyyourdream/blog/867209
// https://chrunlee.cn/article/js-common-denominators.html杨辉三角形
javascript
/*
杨辉三角形：
1) 每一行设为m行, 每行上面的某个元素, 设为第n个元素
2) 每一行上面, 第一个元素为1, 最后一个元素为1
3) 第m行上面, 有m个元素
4) 第m行上面的第n个元素的值, 等于第m-1行上面第n个元素与第m-1行上面第n-1个元素的值的和
用排列组合公式表示为：C(m, n) = C(m-1, n) + C(m -1, n -1)
*/
function combine (m, n) {
if (n == 0) { // 每行第0个元素为1
return 1;
} else if (m == n) { // 每行最后一个元素为1
return 1;
} else { // 其他情况用公式实现
return combine(m - 1, n) + combine(m - 1, n - 1);
}
}
function put (len) {
for (let i = 0; i < len; i++) { // 遍历每一行
for (let j = 0; j <= i; j++) { // 遍历每行上面每个元素
document.write(combine(i, j) + ' ');
}
document.write('<br/>');
}
}
// 更多资料
// https://blog.csdn.net/qq_28534081/article/details/80952856
// https://www.cnblogs.com/zhangzhiyong/archive/2018/09/15/9651965.html
// https://segmentfault.com/a/1190000017758987整数拆分
javascript
// 整数拆分
// https://blog.csdn.net/u011889952/article/details/44813593最长公共子串
javascript
/*
最大公共子串：
给定两个字符串,求出它们的最长公共字串
*/
function findSubStr(str1, str2) {
if (str1.length > str2.length) {
var temp = str1;
str1 = str2;
str2 = temp;
}
var len1 = str1.length,
len2 = str2.length;
for (var j = len1; j > 0; j--) {
for (var i = 0; i < len1 - j; i++) {
var current = str1.substr(i, j);
if (str2.indexOf(current) >= 0) {
return current;
}
}
}
return "";
}
// 更多资料
// https://segmentfault.com/a/1190000007963594
// https://www.cnblogs.com/iyangyuan/p/4470957.html
// https://blog.csdn.net/weixin_33714884/article/details/86446418排序算法
冒泡排序 Bubble Sort
javascript
/*
冒泡排序：
比较每相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一轮就可以选出一个最大的数放在最后面；
那么经过 n-1（数组的 length - 1） 轮，就完成了所有数的排序。
从运行时间的角度来看，冒泡排序是最差的一个。
不推荐该算法，它的复杂度是O(n2)。
*/
// 普通冒泡
function bubbleSort(arr) {
const length = arr.length;
for (let i = 0; i < length - 1; i++) {
let changeOccur = false; //用于标记某次外循环中，是否方式内循环交换事件
for (let j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
changeOccur = true;
}
}
if (!changeOccur) { //如果一次外循环中，没有发生一次内循环交换，那么可以直接结束排序比较
break;
}
}
}
// 双向冒泡
function bubbleSort2(arr) {
const length = arr.length;
let low = 0;
let high = length - 1;
while (low < high) {
let changeOccur = false;
for (let j = low; j < high; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 改用es6的写法
changeOccur = true;
}
}
if (!changeOccur) {
break; // 如果一次交换也没有发生，那直接就可以跳出，结束排序
}
high--;
changeOccur = false;
for (let j = high; j > low; j--) {
if (arr[j] < arr[j - 1]) {
[arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
changeOccur = true;
}
}
if (!changeOccur) {
break;
}
low++;
}
}
// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(bubbleSort(arr));
console.log(bubbleSort2(arr));
// 更多资料
// https://segmentfault.com/a/1190000014175918
// http://www.imooc.com/article/268142?block_id=tuijian_wz
// https://www.cnblogs.com/Bonnie3449/p/9574421.html选择排序 Selection Sort
javascript
/*
选择排序：
初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列。
再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。
依次类推，直到所有元素均排序完毕。
选择排序算法是一种原址比较排序算法。
选择排序同样也是一个复杂度为O(n2)的算法。
*/
function selectionSort(arr) {
for (let i = arr.length - 1; i > 0; i--) {
let maxIndex = i;
for (let j = i - 1; j >= 0; j--) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
if (i !== maxIndex) {
let temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;
}
}
return arr;
}
// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(selectionSort(arr));
// 更多资料
// https://segmentfault.com/a/1190000009366805
// https://blog.csdn.net/bangbanggangan/article/details/81016902
// https://segmentfault.com/a/1190000016006676
// https://www.jianshu.com/p/15799f4c7992插入排序 Insertion Sort
javascript
/*
插入排序：
将未排序数据，对已排序数据序列从后向前扫描，找到对应的位置并插入
排序小型数组时，此算法比选择排序和冒泡排序性能要好。
*/
function insertionSort(arr) {
for (let i = 1, len = arr.length; i < len; i++) {
const temp = arr[i];
let j = i - 1;
while (arr[j] > temp) {
arr[j + 1] = arr[j];
j -= 1;
}
arr[j + 1] = temp;
}
return arr;
}
// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(insertionSort(arr));
// 更多资料
// https://www.cnblogs.com/kongxianghai/p/3998020.html
// https://blog.csdn.net/bangbanggangan/article/details/80986501
// https://segmentfault.com/a/1190000019147630希尔排序 Shell Sort
javascript
/*
希尔排序：
希尔排序是按一定的间隔对数列进行分组，然后在每一个分组中做插入排序；
随后逐次缩小间隔，在每一个分组中做插入排序...
直到间隔等于1，做一次插入排序后结束。
*/
function shellSort(arr) {
const len = arr.length;
let gap = Math.floor(len / 2);
while (gap > 0) {
// 注意下面这段 for 循环和插入排序极为相似
for (let i = gap; i < len; i++) {
const temp = arr[i];
let j = i - gap;
while (arr[j] > temp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(shellSort(arr));
// 更多资料
// https://blog.csdn.net/lhjuejiang/article/details/80505127
// https://segmentfault.com/a/1190000015489853
// https://www.jianshu.com/p/7492408acab5归并排序 Merge Sort
javascript
/**
归并排序：
归并排序是第一个可以被实际使用的排序算法。
归并排序性能不错，其复杂度为O(nlogn)。
Mozilla Firefox使用归并排序作为Array.prototype.sort的实现，而Chrome使用了一个快速排序的变体。
归并排序是一种分治算法。
*/
function mergeSort(arr) {
const len = arr.length;
if (len < 2) { return arr; }
const mid = Math.floor(len / 2);
const left = arr.splice(0, mid);
const right = arr;
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
while (left.length > 0 && right.length > 0) {
result.push(left[0] <= right[0] ? left.shift() : right.shift());
}
return result.concat(left, right);
}
// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(mergeSort2(arr));堆排序 Heap Sort
javascript
/***
堆排序：
堆排序也是一种很高效的算法，因其把数组当作二叉树来排序而得名。
*/
function heapSort(arr) {
let size = arr.length;
// 初始化堆，i 从最后一个父节点开始调整，直到节点均调整完毕
for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
heapify(arr, i, size);
}
// 堆排序：先将第一个元素和已拍好元素前一位作交换，再重新调整，直到排序完毕
for (let i = size - 1; i > 0; i--) {
swap(arr, 0, i);
size -= 1;
heapify(arr, 0, size);
}
return arr;
}
function heapify(arr, index, size) {
let largest = index;
let left = 2 ### index + 1;
let right = 2 ### index + 2;
if (left < size && arr[left] > arr[largest]) {
largest = left;
}
if (right < size && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== index) {
swap(arr, index, largest);
heapify(arr, largest, size);
}
}
// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(heapSort(arr));快速排序 Quick Sort
javascript
/*
快速排序：
选基准：在数据结构中选择一个元素作为基准(pivot)
划分区：参照基准元素值的大小，划分无序区，所有小于基准元素的数据放入一个区间，所有大于基准元素的数据放入另一区间，
分区操作结束后，基准元素所处的位置就是最终排序后它应该所处的位置
递归：对初次划分出来的两个无序区间，递归调用第 1步和第 2步的算法，直到所有无序区间都只剩下一个元素为止。
快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn)，且它的性能通常比其他的复杂度为O(nlogn)的排序算法要好。
和归并排序一样，快速排序也使用分治的方法。
*/
function quickSort(arr) {
const pivot = arr[0];
const left = [];
const right = [];
if (arr.length < 2) { return arr; }
for (let i = 1, len = arr.length; i < len; i++) {
arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
}
return quickSort(left).concat([pivot], quickSort(right));
}
// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(quickSort(arr));
// 更多资料
// https://www.cnblogs.com/LIUYANZUO/p/5745306.html
// https://segmentfault.com/a/1190000014406198
// https://blog.csdn.net/neulily2005/article/details/83577403
// https://www.cnblogs.com/hjx-blog/articles/9183453.html查找/搜索算法
线性查找
javascript
// 线性查找
// 顺序搜索是最低效的一种搜索算法。
function linearSearch(arr, data) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data) {
return i;
}
}
return -1;
}二分查找
javascript
/*
二分查找：
前提：数组、有序。逻辑：优先和数组的中间元素比较，如果等于中间元素，则直接返回。如果不等于则取半继续查找。
二分搜索算法的原理和猜数字游戏类似。
*/
function binarySearch(arr, value) {
let min = 0;
let max = arr.length - 1;
while (min <= max) {
const mid = Math.floor((min + max) / 2);
if (arr[mid] === value) {
return mid;
} else if (arr[mid] > value) {
max = mid - 1;
} else {
min = mid + 1;
}
}
return -1;
}
// 更多资料
// https://blog.csdn.net/phoebe_16/article/details/54613240
// https://www.jianshu.com/p/eef65b21ace0
// https://www.cnblogs.com/YikaJ/p/4387909.html跳转查找
插值查找
javascript
// 插值查找
function InsertionSearch(arr, val, start, end) {
var end = end || data.length - 1;
var start = start || 0;
var mid = start + (val - arr[low]) / (arr[end] - arr[start]) ### (end - start);
if (arr[mid] == val) {
return mid;
}
if (arr[mid] > val) {
return InsertionSearch(arr, val, start, mid - 1);
}
else {
return InsertionSearch(arr, val, mid + 1, end);
}
}[数]深度优先搜索
[数]广度优先搜索
[图]深度优先搜索
[图]广度优先搜索
趣味算法
汉诺塔
旋转矩阵
跳跃游戏
独特路径
雨水收集
递归楼梯
八皇后问题
骑士巡逻
[附]常见的算法范式：
暴力破解法
分治法
动态规划法
贪心算法
回溯法
分支限界法
参考资料
- https://book.douban.com/subject/25945449/
- https://book.douban.com/subject/26979890/
- https://github.com/RayJune/Elegant-JavaScript-Sorting-Algorithms
- https://github.com/jinzhuming/algorithm
- https://github.com/trekhleb/javascript-algorithms/blob/master/README.zh-CN.md
- https://github.com/JesseZhao1990/algorithm