通常情况下，搞金融的都会考算法。

一、排序

说明
时间复杂度指的是一个算法执行所耗费的时间，一般用代码执行的次数
空间复杂度指运行完一个程序所需内存的大小
稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面
不稳定指，如果a=b，a在b的前面，排序后可能会交换位置

基本排序：冒泡、选择、插入
高级排序：希尔、快速、归并

原生js里面的sort方法，在firefox里面是用归并排序实现的，而在chrome里面是用快速排序的变体来实现的。

image.png

1、冒泡排序：

https://www.jianshu.com/p/b5eaf39c4217

原理
冒泡排序（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)

总结
冒泡排序的时间复杂度是n，其中n是要排序的元素个数。由于其性能较差，通常不建议在大型数据集上使用冒泡排序。然而，冒泡排序仍然有其价值：

• 学习排序算法：冒泡排序是理解排序算法的良好起点，它的实现非常简单，有助于初学者理解排序的基本概念。
• 小型数据集：对于小型数据集，冒泡排序可能是一个合理的选择，因为其实现简单且易于编写。

在Java JDK中，冒泡排序通常不会直接用于实际的生产代码中。Java提供了更高效的排序方法，例如Arrays.sort()用于对数组进行排序，以及Collections.sort()用于对集合进行排序，这些方法使用了更高效的排序算法，如快速排序和归并排序。

2、选择排序：

https://www.jianshu.com/p/92226136dcd1

原理
首先从原始数组中找到最小的元素，并把该元素放在数组的最前面，然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，知道排序完毕。

• 平均时间复杂度O(n*n)
• 最好情况O(n*n)
• 最差情况O(n*n)
• 空间复杂度O(1)
• 稳定性：不稳定（例如： 80 80 70，第一个80会和70调换位置，所以不稳定）

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<len-1;i++){
        minIndex=i;
        for(j=i+1;j<len;j++){
            if(arr[j]<arr[minIndex]){
                minIndex=j;
            }
        }
    temp=arr[i];
    arr[i]=arr[minIndex];
    arr[minIndex]=temp;
    }
    console.timeEnd('选择排序耗时');
    return arr;
}
console.log(selectSort(example));

minIndex始终保存着最小值的位置的索引，随着i的自增，遍历的数组长度越来越短，直到完成排序。

选择排序算法虽然不如一些高级排序算法快速，但它易于理解和实现，对于小型数据集或接近排序状态的数据集可能是一个合理的选择。

3、插入排序 （Insertion Sort）

原理
插入排序的核心思想是逐个将未排序的元素插入到已排序的部分中，构建有序序列。这个过程类似于整理扑克牌，每次拿出一张牌并将其插入到已排序的牌堆中。是一种简单但性能较差的排序算法，其性能取决于输入数据的初始顺序。

• 平均时间复杂度O(n*n)
• 最好情况O(n)
• 最差情况O(n*n)
• 空间复杂度O(1) 它只需要常量级别的额外空间来存储临时变量
• 稳定性：稳定

image.png

步骤
插入排序的步骤可以简单概括为以下几个阶段：
1、初始状态： 将数组的第一个元素视为已排序部分，其余部分为未排序部分。
2、逐个插入： 从未排序部分选择一个元素，将其插入到已排序部分的正确位置。为了插入，将已排序部分中大于待插入元素的元素向右移动一个位置。
3、重复： 重复上述插入步骤，直到所有元素都被插入到已排序部分。
4、完成： 当算法完成时，整个数组就被排序了。

image.png

算法

    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