JS常用算法

排序算法

一、冒泡排序

冒泡排序比较任意两个相邻的项，如果第一个比第二个大，则交换他们

function BubbleSort(array){
  var length = array.length;
  for (var i = 0; i < length;i++) {
    for(var j = 0; j < length-i-1; j++){
      if(array[j]>array[j+1]) {
        [array[j], array[j+1]] = [array[j+1], array[j]];
      }
    }
  }
}

二、选择排序

选择排序是找到数据结构中的最小值，并把他放在第一位，接着找到第二小的值并把他放在第二位，以此类推

function selection(array) {
  var length = array.length;
  var minIndex;
  for(var i = 0; i < length-1; i++) {
    minIndex = i;
    for(var j = i; j < length; j++) {
      if(array[minIndex] > array[j]) {
        minIndex = j;
      }
    }
    if(i!=minIndex) {
      [i, minIndex] = [minIndex, i];
    }
  }
}

三、插入排序

插入排序每次排一个数组项，以此方式构建最后的排序数组

function insertSort(array) {
  var length = array.length;
  var j,temp;
  for (var i = 1; i < length; i++) {
    j = i;
    temp = array[i];
    while (j > 0 && array[j-1] > temp) {
      array[j] = array[j-1];
      j--;
    }
    array[j] = temp;
  }
}

四、快速排序

从数组中选择中间一项作为主元。

创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交换他们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。

接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直到数组完全排序。

function quickSort(array, left, right) {
  var index;
  if(array.length > 1) {
    index = partition(array, left, right);
    if(left < index-1) {
      quickSort(array, left, index-1);
    }
    if(index < right) {
      quickSort(array, index, right);
    }
  }
}
 
function partition(array, left, right) {
  /* 选择主元 */
  var pivot = array[Math,floor(left + right)/2];
  var i = left, j = right;
  while(i < j) {
    while(array[i] < array[pivot]) {
      i++;
    }
    while(array[j] > array[pivot]) {
      j--;
    }
    if(i <= j) {
      [array[i], array[j]] = [array[j], array[i]];
      i++;
      j--;
    }
  }
  return i;
}

五、堆排序

构造一个满足array[parent(i)] ≥ array[i]的堆结构。

交换堆里第一个元素（数组中较大的值）和最后一个元素的位置。

第二步可能会丢失堆的属性，因此需再次将数组转换成堆，也就是找到当前堆的根节点（较小的值）重新放到树的底部。

function heapSort(array) {
  var heapSize = array.length;
  buildHeap(array);
  while(heapSize > 1) {
    heapSize--;
    [array[0], array[heapSize]] = [array[heapSize], array[0]];
    heapify(array, heapSize, 0);
  }
}
 
function buildHeap(array) {
  var heapSize = array.length;
  for(var i = Math.floor(heapSize/2; i >= 0; i--)) {
    heapify(array, heapSize, i);
  }
}
 
function heapify(array, heapSize, i){
  var left = i * 2 + 1,
  var right = i * 2 + 2,
  var largest = i;
  if(left < heapSize && array[left] > array[largest]) {
    largest = left;
  }
  if(right < heapSize && array[right] > array[largest]) {
    largest = right;
  }
  if(largest != i) {
    [array[i], array[largest]] = [array[largest], array[i]];
    heapify(array, heapSize, largest);
  }
}

六、归并排序

将两个按值有序序列合并成一个按值有序序列，则称之为二路归并排序。

function merge(left, right) {
  var result = [],
  var il = 0,
  var ir = 0;
  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }
  while(left[il]){
    result.push(left[il++]);
  }
  while(right[ir]){
    result.push(right[ir++]);
  }
  return result;
}

字符串操作

一、判断回文字符串

function palindrome(str){
  // \W匹配任何非单词字符。等价于“[^A-Za-z0-9_]”。
  var re = /[\W_]/g;
  // 将字符串变成小写字符,并干掉除字母数字外的字符
  var lowRegStr = str.toLowerCase().replace(re,'');
  // 如果字符串lowRegStr的length长度为0时，字符串即是palindrome
  if(lowRegStr.length===0)return true;
  // 如果字符串的第一个和最后一个字符不相同，那么字符串就不是palindrome
  if(lowRegStr[0]!=lowRegStr[lowRegStr.length-1])return false;
  //递归
  return palindrome(lowRegStr.slice(1,lowRegStr.length-1));
}

二、翻转字符串

1：反向遍历字符串

function reverseString(str){
  var tmp = '';
  for(var i=str.length-1;i>=0;i--)
    tmp += str[i];
  return tmp
}

2：转化成array操作

function reverseString2(str){
  var arr = str.split("");
  var i = 0,j = arr.length-1;
  while(i<j){
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    j--;
  }
  return arr.join("");
}

• 因为str[i]是只读的，不能str[0]=str[1]这样操作。
• 如果允许用reverse()，也可以用'str'.split('').reverse().join('')实现。

三、生成指定长度随机字符串

配合模糊等效果可以生成个验证码- -

function randomString(n){
  var str = 'abcdefghijklmnopqrstuvwxyz0123456789';
  var tmp = '';
  for(var i=0;i<n;i++)
    tmp += str.charAt(Math.round(Math.random()*str.length));
  return tmp;
}

四、统计字符串中次数最多字母

利用Object中key的唯一性，利用key来进行筛选，然后计数。

function findMaxDuplicateChar(str) {
  if(str.length == 1) {
    return str;
  }
  var charObj = {};
  for(var i = 0; i < str.length; i++) {
    if(!charObj[str.charAt(i)]) {
      charObj[str.charAt(i)] = 1;
    } else {
      charObj[str.charAt(i)] += 1;
    }
  }
  var maxChar = '',
  var maxValue = 1;
  for(var k in charObj) {
    if(charObj[k] >= maxValue) {
      maxChar = k;
      maxValue = charObj[k];
    }
  }
  return maxChar + '：' + maxValue;
}

数组操作

一、数组去重

还是利用Object中key的唯一性，利用key来进行筛选。

function unique(arr){
  var obj = {}
  var data = []
  for(var i in arr){
    if(!obj[arr[i]]){
      obj[arr[i]] = true;
      data.push(arr[i]);
    }
  }
  return data;
}

二、Number数组中最大差值

function getMaxProfit(arr){
  var min = arr[0], max = arr[0];
  for(var i=0;i<arr.length;i++){
    if(arr[i]<min)
      min = arr[i];
    if(arr[i]>max)
      max = arr[i];
  }
  return max - min;
}

其他常见算法

一、阶乘

1：非递归实现

function factorialize(num) {
  var result = 1;
  if(num < 0) return -1;
  if(num == 0 || num == 1) return 1;
  while(num>1)
    result *= num--;
  return result;
}

2：递归实现

function factorialize(num) {
  var result = 1;
  if(num < 0) return -1;
  if(num == 0 || num == 1) return 1;
  if(num > 1){
    return num*factorialize(num-1);
  }
}

二、生成菲波那切数列

斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列主要考察递归的调用。
通过定义fibo[i] = fibo[i-1]+fibo[i-2];来生成斐波那契数组。

1：强行递归实现

function getfib(n){
  if(n == 0)
  return 0;
  if(n == 1)
  return 1;
  if(n > 1){
    return getfib(n-1) + getfib(n-2);
  }
}
function fibo(len){
  var fibo = [];
  for(var i=0;i<len;i++)
    fibo.push(getfib(i));
  return fibo;
}

2：简约非递归版

function getFibonacci(n) {
  var fibarr = [];
  var i = 0;
  while(i < n) {
    if(i <= 1) {
      fibarr.push(i);
    } else {
      fibarr.push(fibarr[i - 1] + fibarr[i - 2])
    }
    i++;
  }
  return fibarr;
}

三、二分查找

二分查找又称折半查找，是在有序数组查找中用到的较为频繁的一种算法
优点是比较次数少，查找速度快，平均性能好；
缺点是要求待查表为有序表，且插入删除困难。

1：非递归实现

function binary_search(arr, key) {
  var low = 0,
  var high = arr.length - 1;
  while(low <= high){
    var mid = parseInt((high + low) / 2);
    if(key == arr[mid]){
      return mid;
    }else if(key > arr[mid]){
      low = mid + 1;
    }else if(key < arr[mid]){
      high = mid -1;
    }
  }
  return -1;
};

2：递归实现

function binary_search2(arr, low, high, key) {
  if(low > high)
    return -1;
  var mid = parseInt((low + high)/2);
  if(key == arr[mid])
    return mid;
  else if(key > arr[mid])
    return binary_search2(arr, mid+1, high, key);
  else if(key < arr[mid])
    return binary_search2(arr, low, mid-1, key);
}