通常情況下，搞金融的都會考算法豹缀。
一坟漱、排序
說明
時間復雜度指的是一個算法執(zhí)行所耗費的時間栏赴，一般用代碼執(zhí)行的次數(shù)
空間復雜度指運行完一個程序所需內(nèi)存的大小
穩(wěn)定指，如果a=b,a在b的前面靖秩，排序后a仍然在b的前面
不穩(wěn)定指须眷，如果a=b，a在b的前面沟突，排序后可能會交換位置
基本排序：冒泡花颗、選擇、插入
高級排序：希爾惠拭、快速扩劝、歸并
原生js里面的sort方法，在firefox里面是用歸并排序?qū)崿F(xiàn)的职辅，而在chrome里面是用快速排序的變體來實現(xiàn)的棒呛。
image.png
1、冒泡排序：
http://www.reibang.com/p/b5eaf39c4217
原理
冒泡排序（Bubble Sorting）域携，是一種計算機科學領(lǐng)域的較簡單的排序算法簇秒。它的基本思想是：通過對待排序序列從前向后（從下標較小的元素開始）, 依次比較相鄰元素的值，若發(fā)現(xiàn)逆序則交換秀鞭，使值較大的元素逐漸從前移向后部趋观，就象水底下的氣泡一樣逐漸向上冒。故名“冒泡排序”锋边。
- 平均時間復雜度O(n*n)
- 最好情況O(n)
- 最差情況O(n*n)
- 空間復雜度O(1)
- 穩(wěn)定性：穩(wěn)定
優(yōu)化后的算法
var examplearr = [5, 4, 3, 2, 1];
function sortarr(arr) {
let len = arr.length;
// 外面循環(huán)是數(shù)組有幾個元素皱坛，就要循環(huán)幾次才能排好序，
// 最后一次數(shù)組已經(jīng)拍好序了豆巨，所不用循環(huán)了所以len-1
for (i = 0; i < len - 1; i++) {
// 每次循環(huán)只要交換len-1次(j最大數(shù)為len-1,所以j+1最大為len換句話說最后個數(shù)剩辟，沒有其他數(shù)可以比較了)
// 每循環(huán)一次，就排好一個數(shù)字所以后面的數(shù)字就不用循環(huán)了所以 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)
總結(jié)
冒泡排序的時間復雜度是n往扔，其中n是要排序的元素個數(shù)贩猎。由于其性能較差，通常不建議在大型數(shù)據(jù)集上使用冒泡排序瓤球。然而融欧，冒泡排序仍然有其價值：
- 學習排序算法：冒泡排序是理解排序算法的良好起點敏弃，它的實現(xiàn)非常簡單卦羡，有助于初學者理解排序的基本概念。
- 小型數(shù)據(jù)集：對于小型數(shù)據(jù)集，冒泡排序可能是一個合理的選擇绿饵，因為其實現(xiàn)簡單且易于編寫欠肾。
在Java JDK中，冒泡排序通常不會直接用于實際的生產(chǎn)代碼中拟赊。Java提供了更高效的排序方法刺桃，例如Arrays.sort()用于對數(shù)組進行排序，以及Collections.sort()用于對集合進行排序吸祟，這些方法使用了更高效的排序算法瑟慈，如快速排序和歸并排序。
2屋匕、選擇排序：
http://www.reibang.com/p/92226136dcd1
原理
首先從原始數(shù)組中找到最小的元素葛碧，并把該元素放在數(shù)組的最前面，然后再從剩下的元素中尋找最小的元素过吻，放在之前最小元素的后面进泼，知道排序完畢。
- 平均時間復雜度O(n*n)
- 最好情況O(n*n)
- 最差情況O(n*n)
- 空間復雜度O(1)
- 穩(wěn)定性：不穩(wěn)定（例如： 80 80 70纤虽，第一個80會和70調(diào)換位置乳绕，所以不穩(wěn)定）
算法
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的自增洋措，遍歷的數(shù)組長度越來越短，直到完成排序杰刽。
選擇排序算法雖然不如一些高級排序算法快速呻纹，但它易于理解和實現(xiàn)，對于小型數(shù)據(jù)集或接近排序狀態(tài)的數(shù)據(jù)集可能是一個合理的選擇专缠。
3雷酪、插入排序 （Insertion Sort）
原理
插入排序的核心思想是逐個將未排序的元素插入到已排序的部分中，構(gòu)建有序序列涝婉。這個過程類似于整理撲克牌哥力，每次拿出一張牌并將其插入到已排序的牌堆中。是一種簡單但性能較差的排序算法墩弯，其性能取決于輸入數(shù)據(jù)的初始順序吩跋。
- 平均時間復雜度O(n*n)
- 最好情況O(n)
- 最差情況O(n*n)
- 空間復雜度O(1)
它只需要常量級別的額外空間來存儲臨時變量 - 穩(wěn)定性：穩(wěn)定
步驟
插入排序的步驟可以簡單概括為以下幾個階段：
1、初始狀態(tài)： 將數(shù)組的第一個元素視為已排序部分渔工，其余部分為未排序部分锌钮。
2、逐個插入： 從未排序部分選擇一個元素引矩，將其插入到已排序部分的正確位置梁丘。為了插入侵浸，將已排序部分中大于待插入元素的元素向右移動一個位置。
3氛谜、重復： 重復上述插入步驟掏觉，直到所有元素都被插入到已排序部分。
4值漫、完成： 當算法完成時澳腹，整個數(shù)組就被排序了。
算法
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]) {
// 調(diào)換兩者的位置
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
}
}
}
return arr
}
var arr = [5, 4, 3, 2, 1];
console.log(insertSort(arr))
總結(jié)
適用性：插入排序適用于小型數(shù)據(jù)集或已接近排序狀態(tài)的數(shù)據(jù)集杨何。對于大型數(shù)據(jù)集酱塔，插入排序的性能會變得相對較差，并且不如一些更高級的排序算法危虱，如快速排序或歸并排序延旧。
優(yōu)點：插入排序的優(yōu)點是實現(xiàn)簡單，易于理解和調(diào)試槽地。在某些情況下迁沫，它可能比其他排序算法更快，尤其是對于小型數(shù)據(jù)集捌蚊。
缺點：插入排序的缺點是其時間復雜度較高集畅，特別是在大型數(shù)據(jù)集上。對于大規(guī)模數(shù)據(jù)缅糟，更高效的排序算法通常更受歡迎挺智。
4、快速排序：
原理
從數(shù)組中選定一個基數(shù)窗宦，然后把數(shù)組中的每一項與此基數(shù)做比較赦颇，小的放入一個新數(shù)組，大的放入另外一個新數(shù)組赴涵。然后再采用這樣的方法操作新數(shù)組媒怯。直到所有子集只剩下一個元素，排序完成髓窜。
- 平均時間復雜度O(nlogn)
- 最好情況O(nlogn)
- 最差情況O(n*n)
- 空間復雜度O(logn)
- 穩(wěn)定性：不穩(wěn)定
解析
pivotIndex是將數(shù)組的長度除2向下取整得到的一個數(shù)值扇苞，數(shù)組的長度是不斷減半的，所以最后它的值為0寄纵，pivot是利用splice方法從數(shù)組里獲取一個基數(shù)
算法
function fastSort(arr) {
let len = arr.length;
if (len < 2) {
return arr
}
let left = [];
let right = [];
let base = Math.floor(len / 2)
// 把基數(shù)3從數(shù)組中去掉鳖敷，此時數(shù)組的長度也變成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])
}
}
// 遞歸操作后把把切割的數(shù)組加進來
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數(shù)組本身就具備堆棧和隊列特性崖媚。
（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
