Javascript Algorithms

JavaScript 算法与数据结构

数据结构

数据结构是在计算机中 组织和存储数 据的一种特殊方式, 它可以高效地 访问和修改 数据。更确切地说, 数据结构是数据值的集合, 它们之间的关系、函数或操作可以应用于数据。

算法

算法是如何解决一类问题的明确规范。 算法是一组精确定义操作序列的规则。

大O符号

大O符号中指定的算法的增长顺序。

源: Big O Cheat Sheet.

数据结构操作的复杂性

以下是一些最常用的 大O标记法 列表以及它们与不同大小输入数据的性能比较。

数组排序算法的复杂性

| 名称 | 最优 | 平均 | 最坏 | 内存 | 稳定 | | ——————— | :——-: | :——-: | :———–: | :——-: | :——-: | | 冒泡排序 | n | n^2 | n^2 | 1 | Yes | | 插入排序 | n | n^2 | n^2 | 1 | Yes | | 选择排序 | n^2 | n^2 | n^2 | 1 | No | | 堆排序 | n log(n) | n log(n) | n log(n) | 1 | No | | 归并排序 | n log(n) | n log(n) | n log(n) | n | Yes | | 快速排序 | n log(n) | n log(n) | n^2 | log(n) | No | | 希尔排序 | n log(n) | 取决于差距序列 | n (log(n))^2 | 1 | No |
首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。

  其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些（个人感觉，没有证实）。

冒泡算法

冒泡排序算法就是依次比较大小，小的的大的进行位置上的交换。

function bubbleSort(arr) {  
    for(let i = 0,l=arr.length;i<l-1;i++) {
        for(let j = i+1;j<l;j++) { 
          if(arr[i]>arr[j]) {
                let tem = arr[i];
                arr[i] = arr[j];
                arr[j] = tem;
            }
        }
    }
    return arr;
}

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

快速排序

算法参考某个元素值，将小于它的值，放到左数组中，大于它的值的元素就放到右数组中，然后递归进行上一次左右数组的操作，返回合并的数组就是已经排好顺序的数组了。

function quickSort(arr) {

    if(arr.length<=1) {
        return arr;
    }

    let leftArr = [];
    let rightArr = [];
    let q = arr[0];
    for(let i = 1,l=arr.length; i<l; i++) {
        if(arr[i]>q) {
            rightArr.push(arr[i]);
        }else{
            leftArr.push(arr[i]);
        }
    }

    return [].concat(quickSort(leftArr),[q],quickSort(rightArr));
}

判断一个单词是否是回文？

回文是指把相同的词汇或句子，在下文中调换位置或颠倒过来，产生首尾回环的情趣，叫做回文，也叫回环。比如 mamam redivider .

function checkPalindrom(str) {  
    return str == str.split('').reverse().join('');
}

去掉一组整型数组重复的值

• 比如输入: [1,13,24,11,11,14,1,2]
• 输出: [1,13,24,11,14,2]
• 需要去掉重复的11 和 1 这两个元素。

/**
* unique an array 
**/
let unique = function(arr) {  
  let hashTable = {};
  let data = [];
  for(let i=0,l=arr.length;i<l;i++) {
    if(!hashTable[arr[i]]) {
      hashTable[arr[i]] = true;
      data.push(arr[i]);
    }
  }
  return data

}

不借助临时变量，进行两个整数的交换

输入 a = 2, b = 4 输出 a = 4, b =2

主要是利用 + - 去进行运算，类似 a = a + ( b - a) 实际上等同于最后 的 a = b;

function swap(a , b) {  
  b = b - a;
  a = a + b;
  b = a - b;
  return [a,b];
}