JavaScript算法
一、算法复杂度
给定一个或多个已知值，通过一系列的运算输出所需结果的过程，叫做算法。一个需求可能可以通过多种算法来实现，学习算法让我们了解怎样的算法效率更高更快，从而让我们针对某个需求做出最合适的选择。作为一名前端攻城狮，算法可能目前离你很远，但是如果你想在编程的路上走的更远一些，或涉猎到更多的数据逻辑，算法对你的帮助很大。所以想成为一名高端的开发者，算法是必须要学习的。
讨论一个算法的好坏，有最主要的两个方面：该算法所需时间-时间复杂度，该算法占用空间（内存）-空间复杂度。耗时短占用低肯定是最优选择，而往往我们需要在两者中找到一个平衡点。作为一名程序开发者，大多数情况下，时间复杂度比空间复杂度的影响更大一些，能做的改良和优化也更多，所以一般如果不做特别说明，我们在讨论算法复杂度的时候都是指时间复杂度。
1. 时间复杂度
一个算法所需要的时间需要具体上机运行才知道，很显然不可能每个都验证一遍再做选择。我们可以对算法耗时进行合理的预测。
一个算法中语句的执行次数我们叫做时间频度，记做T(n)，n表示问题规模，n增大T(n)也随之增大。而我们预估算法的效率，就是对T(n)的变化趋势进行分析，为了方便分析，我们需要简化一下T(n)函数，所以我们引入时间复杂度的概念：若有某个辅助函数 f(n)，使得当n趋近与无穷大时，T(n)/f(n) 的极限值为不等于0的常数，则称 f(n) 是 T(n)的同数量级函数，记做 T(n) = O( f(n) )。O( f(n) )就是时间复杂度的表示法。
总结一下：用O( f(n) )来表示算法时间复杂度。
2. 复杂度计算举例
理论上，我们对 O( f(n) ) 中的 f(n) 没有写法限制，但是因为我们关注的是随 n 增大复杂度的变化趋势，所以各常数项和系数我们是直接省略不做考虑的。
let a = 1;
let b = 2;
console.log(a+b);
//O(1)
let z = 0;
for(let i=0;i<n;i++){
let a = i*2;
z += a;
}
console.log(z);
//O(n)
let c = 0;
for(let i=1;i<n;i++){
for(let j=1;j<n;j++){
c += i*j
}
}
console.log(c);
/*
O(n²)
即使两次循环规模变量n不一样，讨论规模增大时，复杂度的变化趋势，可将即使不一样的规模视作相同变量
*/
let c = 0;
for(let i=1;i<n;i++){
for(let j=i;j<n;j++){
c += i*j
}
}
console.log(c);
//O(n²)
for(let i=1;i<n;i*=2){
console.log(i+1);
}
//O(log₂n)
for(let i=0;i<n;i++){
for(let j=1;j<n;j*=2){
console.log(i+j);
}
}
//O(nlog₂n)
function Fibonacci(n){
if( n<=1 ){
return 1;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
//O(2ⁿ)二、js中常用算法
1.数组整数字去重
//基础写法
function fn(arr){
let newArr = [...arr];
for(let i=newArr.length-1;i>=0;i--){
for(let j=i-1;j>=0;j--){
if( newArr[i] === newArr[j] ){
newArr.splice(j,1);
i --;
}
}
}
return newArr;
}
//O(n^2)
//优化算法复杂度
function fn(arr){
let tmp = {};
let newArr = [];
for(let i=0,length=arr.length;i<length;i++){
let value = arr[i];
if( !tmp[value] ){
tmp[value] = true;
newArr.push(value);
}
}
return newArr;
}
//O(n)注意：Set结构帮助我们实现去重，不代表复杂度为 1 ，因为内部对数组已经进行了遍历，相当于做了封装。
2. 判断回文
数据结构课程中使用栈结构实现了回文，此处我们讨论一下复杂度。
3. 寻找重复最多字符
let str = "abfsafsafghjiq15445454";
function fn(str){
let length = str.length;
let tmp = {};
for(let i=0;i<length;i++){
let val = str.charAt(i);
if( tmp[val] ){
tmp[val] ++;
}else{
tmp[val] = 1;
}
}
let max = 1;
let k = [str.charAt(0)];
for (let [key,value] of Object.entries(tmp)) {
if( value > max ){
k = [key];
max = value;
}else if( value === max ){
k.push(key);
}
}
return k;
}
console.log(fn(str));
//O(n)三、排序算法
1. 冒泡排序
动图演示（动图来源visualgo (opens new window)）：
function bubbleSort (arr) {
let len = arr.length;
//要进行多少轮排序
for(let i = 0; i < len-1; i++) {
//每一轮，相邻两位进行比较，大的放后面
for(let j = 0; j < len-1-i ; j++) {
if( arr[j] > arr[j+1] ){
swap(arr,j,j+1);
}
}
}
}
function swap(arr,i,j){
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
} 2. 选择排序
动图演示（动图来源visualgo (opens new window)）：
function selectionSort(arr){
let len = arr.length;
let minIndex;
for(let i = 0; i < len ; i++) {
minIndex = i;
for(let j = i+1; j < len ; j++) {
if( arr[j] < arr[minIndex] ){
minIndex = j;
}
}
swap(arr,i,minIndex);
}
}
function swap(arr,i,j){
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}3. 插入排序
动图演示（动图来源visualgo (opens new window)）：
function insertSort (arr) {
let len = arr.length;
let j;
let current;
for(let i = 1; i < len; i++) {
current = arr[i];
j = i-1;
while(j>=0 && arr[j] > current){
arr[j+1] = arr[j];
j --;
}
arr[j+1] = current;
}
}4. 归并排序
动图演示（动图来源visualgo (opens new window)）：
//划分
function mergeSort(arr){
let len = arr.length;
if( len < 2 ){
return arr;
}
let mid = Math.floor(len/2);
let left = arr.slice(0,mid);
let right = arr.slice(mid);
return merge(mergeSort(left),mergeSort(right));
}
//排序
function merge(left,right){
let result = [];
while ( left.length > 0 && right.length > 0 ){
if( left[0] <= right[0] ){
result.push( left.shift() );
}else{
result.push( right.shift() );
}
}
while ( left.length ){
result.push( left.shift() );
}
while ( right.length ){
result.push( right.shift() );
}
return result;
}5. 快速排序
动图演示（动图来源visualgo (opens new window)）：
function quickSort(arr){
let len = arr.length;
quick(arr,0,len-1);
}
function quick(arr,left,right){
let point = left;
let index = point+1;
for(let i = index; i <= right; i++) {
if( arr[i] < arr[point] ){
swap(arr,i,index);
index ++;
}
}
swap(arr,point,index-1);
index --;
let leftE = index-1;
let rightB = index+1;
if( leftE > left ){
quick(arr,point,leftE);
}
if( rightB < right){
quick(arr,rightB,right);
}
}
function swap(arr,i,j){
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}6. 堆排序
动图演示（动图来源博客园 (opens new window)）：
function heapSort (arr) {
let len = arr.length;
for(let j = len; j > 1 ; j--) {
let i = Math.floor(j/2) - 1;
heap(arr,i,j);
}
}
function heap (arr,i,len) {
while ( i>=0 ){
let left = 2*i+1,
right = 2*i+2;
let max = arr[i];
let maxIndex = i;
if( left < len && arr[left] > max ){
max = arr[left];
maxIndex = left;
}
if( right < len && arr[right] > max ){
maxIndex = right;
}
swap(arr,i,maxIndex);
i--;
}
swap(arr,0,len-1);
//console.log(arr);
}
function swap(arr,i,j){
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
function heapSort(arr){
let len = arr.length;
//初始堆调整
for(let j = Math.floor(len/2)-1; j >=0 ; j--) {
heap(arr,j,len);
}
for(let i = len-1; i > 0; i--) {
swap(arr,0,i);
len --;
heap(arr,0,len);
}
}
function heap(arr,i,len){
let left = 2*i+1,
right = 2*i+2,
max = arr[i],
maxIndex = i
;
if( left < len && arr[left] > max ){
max = arr[left];
maxIndex = left;
}
if( right < len && arr[right] > max ){
maxIndex = right;
}
if( maxIndex !== i ){
swap(arr,i,maxIndex);
heap(arr,maxIndex,len);
}
}
function swap(arr,i,j){
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}7. 计数排序
动图演示（动图来源博客园 (opens new window)）：
function countSort (arr) {
let count = [];
arr.forEach(item=>{
if(!count[item])count[item] = 0;
count[item] ++;
});
let j = 0;
count.forEach((item,i)=>{
while ( item > 0 ){
arr[j] = i;
item --;
j ++;
}
});
}8. 桶排序
图片展示（图片来源博客园 (opens new window)）：
function quickSort(arr){
let len = arr.length;
quick(arr,0,len-1);
}
function quick(arr,left,right){
let point = left;
let index = point+1;
for(let i = index; i <= right; i++) {
if( arr[i] < arr[point] ){
swap(arr,i,index);
index ++;
}
}
swap(arr,point,index-1);
index --;
let leftE = index-1;
let rightB = index+1;
if( leftE > left ){
quick(arr,point,leftE);
}
if( rightB < right){
quick(arr,rightB,right);
}
}
function swap(arr,i,j){
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
function bucketSort (arr) {
let bucketSize = 10;
let len = arr.length;
let bucketArr = [];
for(let i = 0; i < len; i++)
{
let index = Math.floor(arr[i]/bucketSize);
if( !bucketArr[index] )bucketArr[index] = [];
bucketArr[index].push(arr[i]);
}
let j = 0;
for(let i = 0,len = bucketArr.length; i <len ; i++) {
let item = bucketArr[i];
if( !item )continue;
quickSort(item);
item.forEach(v=>{
arr[j ++] = v;
});
}
}9. 基数排序
动图演示（动图来源博客园 (opens new window)）：
function radixSort (arr) {
let len = arr.length;
//找出数组中最大数的位数
let maxNum = arr[0];
let radixArr = [];
for(let i = 1; i < len; i++) {
if( arr[i] > maxNum ){
maxNum = arr[i];
}
}
let maxDigit = maxNum.toString().length;
let x = 10,y = 1;
for(let i = 0; i < maxDigit; i++) {
for(let j = 0; j < len; j++) {
let v = Math.floor(arr[j] % x / y);
if( !radixArr[v] )radixArr[v] = [];
radixArr[v].push(arr[j]);
}
x *= 10;
y *= 10;
let index = 0;
for(let j = 0,len = radixArr.length; j <len ; j++) {
let item = radixArr[j];
if(!item)continue;
item.forEach(v=>{
arr[index ++] = v;
});
}
radixArr = [];
}
}
评论（0）
暂无评论