通常情况下，搞金融的都会考算法。
一、排序
说明
时间复杂度指的是一个算法执行所耗费的时间
空间复杂度指运行完一个程序所需内存的大小
稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面
不稳定指，如果a=b，a在b的前面，排序后可能会交换位置
基本排序：冒泡、选择、插入
高级排序：希尔、快速、归并
原生js里面的sort方法，在firefox里面是用归并排序实现的，而在chrome里面是用快速排序的变体来实现的。
1、冒泡排序： https://www.jianshu.com/p/b5eaf39c4217
文章图片
image.png
原理
冒泡排序（Bubble Sorting），是一种计算机科学领域的较简单的排序算法。它的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）, 依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。故名“冒泡排序”。- 平均时间复杂度O(n*n)
- 最好情况O(n)
- 最差情况O(n*n)
- 空间复杂度O(1)
- 稳定性：稳定
文章图片
image.png 优化后的算法
var examplearr = [5, 4, 3, 2, 1];
function sortarr(arr) {
let len = arr.length;
// 外面循环是数组有几个元素，就要循环几次才能排好序，
// 最后一次数组已经拍好序了，所不用循环了所以len-1
for (i = 0;
i < len - 1;
i++) {
// 每次循环只要交换len-1次(j最大数为len-1,所以j+1最大为len换句话说最后个数，没有其他数可以比较了)
// 每循环一次，就排好一个数字所以后面的数字就不用循环了所以 len - 1 - i
for (j = 0;
j < len - 1 - i;
j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]//es6s
}
}
}
return arr;
}
sortarr(examplearr);
console.log(examplearr);
//封装
Array.prototype.doubbleSort = function () {
let arr = this, len = this.length;
for (let i = 0;
i < len - 1;
i++) {
for (let j = 0;
j < len - i - 1;
j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr
}
let newArr = [5, 4, 3, 2, 1].doubbleSort()
console.log(newArr)
2、选择排序： https://www.jianshu.com/p/92226136dcd1
原理
首先从原始数组中找到最小的元素，并把该元素放在数组的最前面，然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，知道排序完毕。- 平均时间复杂度O(n*n)
- 最好情况O(n*n)
- 最差情况O(n*n)
- 空间复杂度O(1)
- 稳定性：不稳定
文章图片
image.png 【前端算法基础】算法
var example=[8,94,15,88,55,76,21,39];
function selectSort(arr){
var len=arr.length;
var minIndex,temp;
console.time('选择排序耗时')；
for(i=0;
i
minIndex始终保存着最小值的位置的索引，随着i的自增，遍历的数组长度越来越短，直到完成排序。
3、插入排序
https://www.jianshu.com/p/fd789c9c382c
原理
用未参与排序的数与已经排好序的数从后往前做比较,比较中找到自己的位置然后插入到该位置
- 平均时间复杂度O(n*n)
- 最好情况O(n)
- 最差情况O(n*n)
- 空间复杂度O(1)
- 稳定性：稳定
算法
function insertSort(arr) {
var len = arr.length;
for (var i = 1;
i < len;
i++) {
for (var j = i;
j > 0;
j--) {
if (arr[j] < arr[j - 1]) {
// 调换两者的位置
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
}
}
}
return arr
}
var arr = [5, 4, 3, 2, 1];
console.log(insertSort(arr))
4、快速排序：
原理
从数组中选定一个基数，然后把数组中的每一项与此基数做比较，小的放入一个新数组，大的放入另外一个新数组。然后再采用这样的方法操作新数组。直到所有子集只剩下一个元素，排序完成。
- 平均时间复杂度O(nlogn)
- 最好情况O(nlogn)
- 最差情况O(n*n)
- 空间复杂度O(logn)
- 稳定性：不稳定
解析
pivotIndex是将数组的长度除2向下取整得到的一个数值，数组的长度是不断减半的，所以最后它的值为0，pivot是利用splice方法从数组里获取一个基数
算法
function fastSort(arr) {
let len = arr.length;
if (len < 2) {
return arr
}
let left = [];
let right = [];
let base = Math.floor(len / 2)
// 把基数3从数组中去掉，此时数组的长度也变成4了
let baseNum = arr.splice(base, 1)[0]
for (i = 0;
i < arr.length;
i++) {
if (baseNum > arr[i]) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
// 递归操作后把把切割的数组加进来
return fastSort(left).concat([baseNum], fastSort(right))
}
console.log(fastSort([5, 4, 3, 2, 1]))
5、归并排序
6、希尔排序
https://segmentfault.com/a/1190000009461832
二、堆栈、队列、链表
堆栈：https://juejin.im/entry/58759e79128fe1006b48cdfd
队列：https://juejin.im/entry/58759e79128fe1006b48cdfd
链表：https://juejin.im/entry/58759e79128fe1006b48cdfd
（1）js数组本身就具备堆栈和队列特性。
（2）堆栈：先进后出。
三、递归
递归：https://segmentfault.com/a/1190000009857470
（1）60%的算法题都用到递归。
四、波兰式和逆波兰式
理论：http://www.cnblogs.com/chenying99/p/3675876.html
源码：https://github.com/Tairraos/rpn.js/blob/master/rpn.js
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
