yunyu950908 / algo Goto Github PK

View Code? Open in Web Editor NEW

0.0 0.0 0.0 23 KB

算法学习

JavaScript 86.60% Python 13.40%

algo's People

Contributors

Watchers

algo's Issues

队列

PS: 个人笔记，写的比较乱。有错误还请指出。

特性

队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。

队列用于存储按顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处
理。

队列的实现

向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。
入队操作在队尾插入新元素，出队操作删除队头的元素。

为了偷懒，继续使用之前的双向链表。
https://github.com/yunyu950908/algorithms/blob/master/data_structure/linked.js
当然，也可以使用数组作为队列的底层数据结构。

Linked 双向链表

/**
 * Node 定义一个节点
 * @param element
 * @param prev
 * @param next
 * */
class Node {
  constructor(element, prev = null, next = null) {
    this.element = element;
    this.prev = prev;
    this.next = next;
  }
}

/**
 * Linked 双向链表
 *
 * 属性
 * head 表头
 * tail 表尾
 *
 * 方法
 * push 入队操作
 * shift 出队操作
 * */
class Linked {
  constructor({ head = null, tail = null, size = 0 } = {}) {
    this.head = head || new Node('Head');
    this.tail = tail || this.head;
    this.size = size;
  }

  push(element) {
    const newNode = new Node(element);
    if (this.tail === this.head) { // 空表
      this.tail = newNode;
      this.tail.prev = this.head;
      this.head.next = this.tail;
    } else { // 非空表
      const tempTail = this.tail;
      this.tail = newNode;
      this.tail.prev = tempTail;
      tempTail.next = this.tail;
    }
    this.size++;
    return this.size;
  }

  shift() {
    const targetNode = this.head.next;
    if (!targetNode) return null;
    if (targetNode === this.tail) {
      this.tail = this.head;
    } else {
      this.head.next.prev = this.head;
    }
    this.head.next = targetNode.next;
    targetNode.next = null;
    targetNode.prev = null;
    this.size--;
    return targetNode;
  }
}

Queue 队列

/**
 * Queue
 *
 * 属性
 * head 队头
 * tail 队尾
 * size
 *
 * 方法
 * push
 * shift
 * */

class Queue {
  constructor() {
    return new Linked();
  }
}

队列的应用

基数排序：

参考：https://visualgo.net/en/sorting

function radixSort(array) {
  const queues = Array.from(new Array(10), () => new Queue());
  const maxLen = Math.max.apply(null, array).toString().length;
  for (let i = 0; i < maxLen; i++) {
    distribute(array, queues, i);
  }
  return array;
}

function distribute(array, queues, digit) {
  let count = 0;
  for (let i = 0; i < array.length; i++) {
    const item = array[i];
    const idx = Math.floor((item / Math.pow(10, digit)) % 10);
    queues[idx].push(item);
  }
  for (let i = 0; i < queues.length; i++) {
    const queue = queues[i];
    while (queue.length > 0) {
      array[count++] = queue.shift();
    }
  }
}

当然队列还有很多其他应用，比如排队挂号，特权插队，限制任务数量等等都可以用队列实现。

记住队列的特征：

先入先出；
队头出队，队尾入队；

sort: selection

选择排序

reference: https://visualgo.net/en/sorting
由于本宝宝是第一次学习，一边学习一边记录，难免会有错误，还请大佬指出，不胜感激~

排序说明

选择排序和冒泡排序同样也是基于比较的排序，需要两个嵌套的循环。

外循环

假定第一个元素是最小/最大的水元素，记录游标。(1)
外循环每次迭代，即有一个元素被交换到了正确的位置，移动游标到下一个要排序的元素。(4)
外循环结束，排序结束。(5)

内循环

内循环遍历外循环记录的游标之后或之前的每个元素；(2)
通过比较找出最小/最大的元素，最后与外循环记录的元素交换。(3)
内循环结束后，外循环移动游标到下一个要排序的元素，开始新一轮的内循环。(4)

�由上述说明，大致上一共有 5 个过程。

Tips: 选择排序交换元素时候会打破原来相同值得元素之间的顺序。比如 const arr = [2,2,1,3]，正向排序时，arr[0] 将与 arr[2] 交换，那么两个数字2（arr[0] arr[1]）之间的顺序将和原来的顺序不一致，虽然它们的值相同，但它们相对的顺序却发生了变化。这种现象称作 不稳定性。

代码实现

先贴上可视化学习资料：https://visualgo.net/en/sorting

以及右下角的伪代码

repeat (numOfElements - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position

第一版：
直接照着伪代码写成 JS

// swap 函数交换元素
function swap(a, b, array) {
  const temp = array[a];
  array[a] = array[b];
  array[b] = temp;
  return null;
}

// selectionSort
function selectionSort(array) {
  // 外循环 n - 1 次操作排完 n 个元素
  for (let i = 0; i < array.length - 1; i++) {
    let minimum = i; // 记录下标
    for (let j = i; j < array.length; j++) {
      // 内循环遍历其他元素，替换正确的最小值下标
      if (array[j] < array[minimum]) minimum = j;
    }
    // 内循环结束后交换 正确的最小值 到 最初记录的未排序元素的位置
    swap(i, minimum, array);
  }
  return array;
}

测试一下，emmmm... 看起来是没啥问题...

源码及测试：https://github.com/yunyu950908/algorithms/blob/master/test/sort_selection.js

复杂度分析

选择排序的复杂度分析跟冒泡差不多，不同之处在于即使最初的数组已经排好序，选择排序还是得自个儿确认一遍，有点蠢萌蠢萌的

外循环：最好 O(n)，最坏 O(n)，
内循环：最好 O(n)，最坏 O(n)

结果应该是

时间复杂度：最好 O(n²)，最坏 O(n²)，平均 O(n²)
空间复杂度：O(1)

大概就酱啦~ 代码应该写的很清楚了，还有不明白的或者是写错了的，欢迎交流纠正~
源码和测试在这里 https://github.com/yunyu950908/algorithms/blob/master/test/sort_selection.js

data_structure: LinkedList

链表

PS: 这里只是个人笔记。

特性

数组：

查找 / 访问 / 遍历相对快。
删除 / 插入相对慢（大量索引变动的情况下）。

链表：

查找 / 访问 / 遍历相对慢。
删除 / 插入相对快。

定义链表

链表是由一组节点组成的集合。
每个节点都使用一个对象的引用指向它的后继。
指向另一个节点的引用叫做链

单向链表
增加元素
删除元素

设计链表

Node 类用来表示节点；
LinkedList 类提供了插入节点、删除节点、显示列表元素以及其他一些辅助方法。

下面的代码实际上还是有问题的，只用于提供思路 =。=

/**
 * Node 定义一个节点
 * @param element
 * @param next
 * */
class Node {
  constructor(element, next) {
    this.element = element;
    this.next = next;
  }
}

/**
 * LinkedList 定义一个链表
 *
 * 属性
 * head 表头
 * tail 表尾
 *
 * 方法
 * insert 插入一个节点
 * remove 删除一个节点
 * find 查找一个节点
 * push 表尾添加一个节点
 * shift 表头删除一个节点
 * display 显示当前链表中的元素
 * */
class LinkedList {
  constructor() {
    this.tail = null;
    this.head = new Node(null, this.tail); // 表头的 element 始终占 null
    this.size = 0;
  }

  push(element) {
    const newNode = new Node(element, null);
    if (!this.tail) { // 空表
      this.tail = newNode;
      this.head.next = this.tail;
    } else { // 非空表
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
    return this.size;
  }

  shift() {
    const targetNode = this.head.next;
    if (!targetNode) return null;
    this.head.next = targetNode.next;
    targetNode.next = null;
    this.size--;
    if (targetNode === this.tail) this.tail = null;
    return targetNode;
  }

  insert(element, after) {
    const newNode = new Node(element, null);
    const afterEle = this.find(after);
    if (!afterEle) return false;
    newNode.next = afterEle.next;
    afterEle.next = newNode;
    this.size++;
    return true;
  }

  remove(element) {
    let curNode = this.head;
    while (curNode.next) {
      if (curNode.next.element === element) {
        const prevNode = curNode;
        const targetNode = curNode.next;
        prevNode.next = targetNode.next;
        targetNode.next = null;
        this.size--;
      }
      curNode = curNode.next;
    }
  }

  find(element) {
    let curNode = this.head;
    while (curNode.next !== null) {
      curNode = curNode.next;
      if (curNode.element === element) return curNode;
    }
    return null;
  }

  display() {
    let curNode = this.head;
    while (curNode.next !== null) {
      curNode = curNode.next;
      console.log(curNode);
    }
  }
}

代码地址：https://github.com/yunyu950908/algorithms/blob/master/data_structure/linked_list.js

试试性能

function competingTest() {
  console.time('generate a big Array from new Array');
  const newArr = new Array(1e7);
  for (let i = 0; i < newArr.length; i++) {
    newArr[i] = i;
  }
  console.timeEnd('generate a big Array from new Array');

  console.time('generate a big Array form Array.prototype.push');
  const newArr2 = [];
  for (let i = 0; i < 1e7; i++) {
    newArr2.push(i);
  }
  console.timeEnd('generate a big Array form Array.prototype.push');

  console.time('operate a big Array');
  for (let i = 0; i < 100; i++) {
    newArr.shift();
  }
  console.timeEnd('operate a big Array');

  console.time('generate a big LinkedList');
  const newLinkedList = new LinkedList();
  for (let i = 0; i < 1e7; i++) {
    newLinkedList.push(i);
  }
  console.timeEnd('generate a big LinkedList');

  console.time('operate a big LinkedList');
  for (let i = 0; i < 100; i++) {
    newLinkedList.shift();
  }
  console.timeEnd('operate a big LinkedList');
}

competingTest();

generate a big Array from new Array: 80.954ms
generate a big Array form Array.prototype.push: 287.428ms
operate a big Array: 1457.407ms
generate a big LinkedList: 1678.951ms
operate a big LinkedList: 0.112ms

emmmmmmm，偷偷试了几次不同的操作数，数组大量的索引变动程线性增长。链表由于每次元素变动最多只改变目标元素和前后两个元素的索引，所以相对快很多。但在空间占用和初始化速度逊色于数组。

new Array(1e7) 直接申请了 1e7 的空间，后续直接用下标赋值。
[].push 在数组元素数量达到某个量级的时候会有一个拷贝的操作，将当前内存中的数组拷贝到一块更大的内存中去。

双向链表

双向链表
删除元素

循环链表

循环链表

sort: quick

快速排序

reference: https://visualgo.net/en/sorting
由于本宝宝是第一次学习，一边学习一边记录，难免会有错误，还请大佬指出，不胜感激~

排序说明

随笔

最一件事情最好的时期是十年前，其次是现在。

这个仓库主要用来记录一些算法学习的笔记（其余笔记以后可能会陆续整理出来），其次是对某些情况的吐槽，希望入行的新人能避坑。

先吐吐苦水。其实很久之前就想补计算机基础，尤其是算法这块儿。然而 996 的生活每天都很疲惫。

新人千万要看清 996 是什么样的 996，如果是在公司自主学习，可以有，如果是无意义的加班，钱给的再多，也还是走人吧，做程序员，生命和知识更重要。

我这 996 口怕的是每天都在重复劳作，每天修不完的bug，以及有从不按开发规范工作的 "我可是有 X 年工作经验的老员工，你得听我的。" 这样的老大，实力强就算了，然而写的代码是我有史以来见过的最丑的。

仔细想想离职原因大致有以下几点太不符合我的代码审美（三观不合）：

滥用全局变量。经常是满屏幕的模块全局变量，以及从不在约定的区域定义的项目全局变量，真的是爱写哪儿写哪儿，怎么写的爽怎么写。不知道是不是别个公司前端也这样玩，不过宝宝勉强能忍受。
无意义的变量名。英语基础差就算了，也不知道用个翻译工具，经常出现一会儿英语一会儿拼音，一会儿又是 aa bb cc 这样毫无意义的变量名。如果只是这样，宝宝其实还阔以忍。
从不降低复杂度。有时候后台确实给了一个稍微有点儿复杂的 JSON，结果后来我维护时看到的代码是这样的：

for (const b of a) {
  for (const c of b) {
    for (const d of c) {
      if (xxx) {
        for (const e of d) {
          // do something
        }
      }
    }
  }
}

结果写出这代码的本人都看不懂自己写的什么玩意儿。这点几乎不能忍。（然而这并不是最不能忍受的）

学习驱动力差。新项目，新代码，居然还有 callback hell，明明 ES6+ 提供了很多便捷的语法糖，却还要我一层层抽丝剥茧阅读代码。'为什么不用新语法？', '不会。'。23333333 ┑(￣Д ￣)┍ 无力反驳。
不写注释。emmmmm，看到上面这几条后，不写注释能忍？？？ excuse me？写几句注释能增加多少开发时间？？？
最后，真的真的真的，X年工作经验 的 高级前端工程师 居然真的只会写前端，而且还写成这样的，真的是头一次见，虽然我也是毕业 ==> 宅家学习 ==> 转行 ==> 入行工作，虽然入行工作没多久，但这 老大 实力也太差了点。绝对不能忍，离职闪人。
加一点，灰常不能忍的，经常不给人 review 就自顾自合代码了... 不知道说什么好...
不能只说缺点，优点还是有的，毕竟工作经验多，踩的坑确实也多，有独特的 debug 技巧，不过貌似写 bug 能力也很强。

哎呀，好像吐完苦水已经这么多字了，这篇就这样吧，总之，遇到这样的公司这样的老大，赶紧把能学的技能学差不多了闪人吧。。长此以往，基本上是学不到东西的，还搭上了自己的青春和生命，更现实的是还没多少钱给你2333333333。

2018-05-13，嘉定。

sort: bubble

冒泡排序

reference: https://visualgo.net/en/sorting
由于本宝宝是第一次学习，一边学习一边记录，难免会有错误，还请大佬指出，不胜感激~

排序说明

冒泡排序需要两个嵌套的循环。

外循环

外循环确定当前要进行排序的游标。(1)
外循环每次迭代，即有一个元素被交换到了正确的位置，移动游标到下一个要排序的元素。(4)
外循环结束，排序结束。(5)

内循环

内循环遍历游标之后或之前的每个元素；(2)
通过两两交换，每轮循环周期结束，即有一个元素被交换到了正确的位置。(3)
内循环结束后，外循环移动游标到下一个要排序的元素，开始新一轮的内循环。(4)

�由上述说明，大致上一共有 5 个过程。

Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

代码实现

先贴上可视化学习资料：https://visualgo.net/en/sorting

以及右下角的伪代码

do
  swapped = false
  for i = 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap(leftElement, rightElement)
      swapped = true
while swapped

第一版：
直接照着伪代码写成 JS

// swap 函数交换元素
function swap(a, b, array) {
  const temp = array[a];
  array[a] = array[b];
  array[b] = temp;
  return null;
}

// bubbleSort
function bubbleSrot(array) {
  // 为方便比较，拷贝一份副本
  const resultArr = [].concat(array);
  // 判断是否交换的 flag
  let swapped = false;
  // 最后一个未排序元素的下标
  let indexOfLastUnsortedElement = resultArr.length - 1;
  do {
    swapped = false;
    // i 的范围 [0, indexOfLastUnsortedElement - 1]
    for (let i = 0; i < indexOfLastUnsortedElement; i += 1) {
      // 如果当前项比后一项大，交换位置
      if (resultArr[i] > resultArr[i + 1]) {
        swap(i, i + 1, resultArr);
        swapped = true;
      }
    }
    // 内循环结束后最后一项为数组最大的元素，之后的内循环元素无需与之比较
    indexOfLastUnsortedElement -= 1;
  } while (swapped);
  return resultArr;
}

测试一下：

// 生成一个包含 10 个 [0, 99] 随机数的数组
function genArr() {
  return Array.from(new Array(10), () => Math.random() * 100 >>> 0);
}

const newArr = genArr();
const sortedArr = bubbleSrot(newArr);
console.log('原数组:', newArr); //原数组: [ 62, 55, 92, 25, 68, 61, 3, 19, 79, 80 ]
console.log('bubbleSrot: ', sortedArr); // bubbleSrot: [ 3, 19, 25, 55, 61, 62, 68, 79, 80, 92 ]

未完待续...

2018-05-14 续

emmm，第一版看起来是没什么问题，不过我还是更喜欢写成 for 循环，毕竟平时撸项目代码基本都是直接用原生封装的 API，不然就是 for... 233333，说干就干，改写一下下。。。

第二版
将原来对着伪代码撸的 do...while + for... 改成 for... + for...

function bubbleSort2(array) {
  // 同样拷贝一份副本，为了后续对比方便
  const resultArr = [].concat(array);
  // 外循环，最多需要 n-1 次排完 n 个元素
  for (let i = 0; i < resultArr.length - 1; i += 1) {
    let isSwap = false;
    // 内循环，最多比较 n - 1 -i 次能得到一个最大的元素
    for (let j = 0; j < resultArr.length - 1 - i; j += 1) {
      if (resultArr[j] > resultArr[j + 1]) {
        swap(j, j + 1, resultArr);
        isSwap = true;
      }
    }
    if (!isSwap) break;
  }
  return resultArr;
}

测试一下下：

const newArr = genArr();
const sortedArr2 = bubbleSrot2(newArr);
console.log('原数组:', newArr); //原数组: [ 66, 5, 33, 35, 96, 83, 44, 6, 95, 49 ]
console.log('bubbleSrot2: ', sortedArr2); // bubbleSrot2: [ 5, 6, 33, 35, 44, 49, 66, 83, 95, 96 ]

冒泡排序是内外两重循环的比较排序，不同的遍历方向可以有 外正内正 外正内负 外负内负 外负内正 这四种写法，具体代码不贴了，一起学习的小伙伴阔以将自己的代码贴出来，一起讨论讨论，虽然对于科班童鞋来说可能都是基础中的基础，然而跟我野路子出生基础奇差的小伙伴阔以一起交流讨论哈~

举个不同遍历方向的例子：
正反双向冒泡排序

function bubbleSort3(array) {
  const resultArr = [].concat(array); // 没错，又是没用的拷贝副本
  let len = resultArr.length;
  for (let i = 0; i < resultArr.length >> 1;) {
    let isSwap = false;
    // 最小的冒泡到最前面
    for (let j = len - 1; j > i; j -= 1) {
      if (resultArr[j] < resultArr[j - 1]) {
        swap(j, j - 1, resultArr);
        isSwap = true;
      }
    }
    if (!isSwap) break;
    isSwap = false;
    // 此时第 i 项已经排好，下一次正向冒泡游标向后移动一位
    i += 1;
    // 最大的冒泡到最后面
    for (let k = i; k < len - 1; k += 1) {
      if (resultArr[k] > resultArr[k + 1]) {
        swap(k, k + 1, resultArr);
        isSwap = true;
      }
    }
    if (!isSwap) break;
    // 此时第 len - 1 项已经排好，下一次负向冒泡起始游标向前移动一位
    len -= 1;
  }
  return resultArr;
}

测试一下：

const newArr = genArr();
const sortedArr3 = bubbleSrot3(newArr);
console.log('原数组:', newArr); // 原数组： [ 30, 65, 27, 99, 50, 54, 67, 94, 19, 93 ]
console.log('bubbleSrot3: ', sortedArr3); // bubbleSrot3：[ 19, 27, 30, 50, 54, 65, 67, 93, 94, 99 ]

emmmm... 看起来是没啥问题哦...

复杂度分析

冒泡排序的复杂度分析相对简单，不过也不太清楚这么想对不对（只看过大话数据结构的理解）

外循环：最好 O(1)，最坏 O(n)，
内循环：最好 O(n)，最坏 O(n)

所以结果应该是

时间复杂度：最好 O(n)，最坏 O(n²)，平均 O(n²)
空间复杂度：不算副本的空间，就只有一个 swap temp 的临时交换空间，所以是 O(1)

大概就酱啦~ 代码应该写的很清楚了，还有不明白的或者是写错了的，欢迎交流纠正~
源码和测试在这里 https://github.com/yunyu950908/algorithms/blob/master/test/sort_bubble.js

data_structure: Stack

栈

PS: 个人笔记，写的比较乱。有错误还请指出。

特性

栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。栈的使用遍布程序语言实现的方方面面，从表达式求值到处理函数调用。

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。
栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。
由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元
素，必须先拿掉上面的元素。
对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用push() 方法，出
栈使用pop() 方法。

栈的实现

为了偷懒，直接用了之前写的链表，不过稍微改了改，改成了一个双向链表。
https://github.com/yunyu950908/algorithms/blob/master/data_structure/linked.js
当然你也可以用数组作为栈的底层数据结构。

Linked 双向链表

/**
 * Node 定义一个节点
 * @param element
 * @param prev
 * @param next
 * */
class Node {
  constructor(element, prev = null, next = null) {
    this.element = element;
    this.prev = prev;
    this.next = next;
  }
}

/**
 * Linked 双向链表
 *
 * 属性
 * head 表头
 * tail 表尾
 *
 * 方法
 * push
 * pop
 * */
class Linked {
  constructor({ head = null, tail = null, size = 0 } = {}) {
    this.head = head || new Node('Head');
    this.tail = tail || this.head;
    this.size = size;
  }

  push(element) {
    const newNode = new Node(element);
    if (this.tail === this.head) { // 空表
      this.tail = newNode;
      this.tail.prev = this.head;
      this.head.next = this.tail;
    } else { // 非空表
      const tempTail = this.tail;
      this.tail = newNode;
      this.tail.prev = tempTail;
      tempTail.next = this.tail;
    }
    this.size++;
    return this.size;
  }

  pop() {
    if (this.tail === this.head) return null;
    const tempTail = this.tail;
    this.tail = tempTail.prev;
    this.tail.next = null;
    tempTail.prev = null;
    this.size--;
    return tempTail;
  }
}

Stack 栈

/**
 * Stack
 *
 * 方法
 * push
 * pop
 * */
class Stack {
  constructor() {
    return new Linked();
  }
}

栈的应用

回文

// 回文测试
function reverse(str) {
  const stack = new Stack();
  let result = '';
  for (let i = 0; i < str.length; i++) {
    stack.push(str[i]);
  }
  for (let i = 0; i < str.length; i++) {
    result += stack.pop().element;
  }
  return result;
}

const str1 = 'hello world';
console.log(`original string: ${str1}`);
console.log(`reserve string: ${reverse(str1)}`);

// original string: hello world
// reserve string: dlrow olleh

递归

// 递归测试
function factorial(n) {
  if (n === 0) return 1;
  else return n * factorial(n - 1);
}

console.log(`factorial: ${factorial(5)}`);

function fact(n) {
  const stack = new Stack();
  while (n > 1) {
    stack.push(n--);
  }
  let result = 1;
  while (stack.size > 0) {
    result *= stack.pop().element;
  }
  return result;
}

console.log(`stack factorial: ${fact(5)}`);

// factorial: 120
// stack factorial: 120

括号匹配，返回缺少括号的位置

// 括号匹配测试
function checkBrace(target) {
  const result = {
    left: [],
    right: [],
  };
  const stack = new Stack();
  for (let i = 0; i < target.length; i++) {
    if (target[i] === '(') stack.push(i);
    if (target[i] === ')') {
      const flag = stack.pop();
      if (!flag) result.right.push(i);
    }
  }
  let curNode = stack.head;
  while (curNode.next) {
    curNode = curNode.next;
    result.left.push(curNode.element);
  }
  return result;
}

console.log(checkBrace('(2.3 + 23) / (12 + (3.14159×0.24)'));
console.log(checkBrace('(2.3 + 23) / (12 + (3.14159×0.24))))'));
console.log(checkBrace('(2.3 + 23) / (((((12 + (3.14159×0.24))))'));

// { left: [ 13 ], right: [] }
// { left: [], right: [ 34, 35 ] }
// { left: [ 13, 14 ], right: [] }

https://github.com/yunyu950908/algorithms/blob/master/data_structure/stack.js

/**
 现实生活中栈的一个例子是佩兹糖果盒。想象一下你有一盒佩兹糖果，里面塞满了红
 色、黄色和白色的糖果，但是你不喜欢黄色的糖果。使用栈（有可能用到多个栈）写一
 段程序，在不改变盒内其他糖果叠放顺序的基础上，将黄色糖果移出。
 * */

sort: merge

归并排序

reference: https://visualgo.net/en/sorting
由于本宝宝是第一次学习，一边学习一边记录，难免会有错误，还请大佬指出，不胜感激~

排序说明

归并排序和前面的几种排序略有不同，前面的三个排序算法的时间复杂度度为O(n²)，在处理大量数据的时候会有明显的性能下降，但归并排序性能不错，复杂度只有 O(nlogn)（PS: 本质上是空间换时间的一种做法）。
归并排序运用了分治**，将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

这货步骤不太好用文字描述，直接看动画演示吧：https://visualgo.net/en/sorting

Tips: 归并排序严格按照从左往右(或从右往左)的顺序去合并子数组, 它并不会改变相同元素之间的相对顺序, 因此它也是一种稳定的排序算法.

代码实现

function mergeSort(array) {
  const length = array.length;
  if (length === 1) return array; // 只剩一项，直接返回
  const mid = length >> 1; // 二分
  const left = array.slice(0, mid); // 前半段数组
  const right = array.slice(mid); // 后半段数组
  return merge(mergeSort(left), mergeSort(right)); // 递归调用
}

function merge(leftArray, rightArray) {
  const result = [];
  let l = 0, r = 0; // 两段数组的索引
  // 从小到大的排序
  while (l < leftArray.length && r < rightArray.length) {
    if (leftArray[l] <= rightArray[r]) {
      result.push(leftArray[l++]);
    } else {
      result.push(rightArray[r++]);
    }
  }
  while (l < leftArray.length) {
    result.push(leftArray[l++]);
  }
  while (r < rightArray.length) {
    result.push(rightArray[r++]);
  }
  return result;
}

/**
 * 实际上这里用 push 添加元素是不太好的，动态增加数组元素一旦达到某个量级之后，
 * 实际上会偷偷执行一个拷贝的动作，将当前内存的数组拷贝到一个更大的内存中去，
 * 所以会有一定的性能损耗，而且这个损耗会随着数组长度的增加而增加，
 * 因此最好使用 new Array(initialLength) 直接申请一个确定长度的空间来初始化数组，
 * 测试文件中已修改。
 * */

测试一下，emmmm... 看起来是没啥问题...

源码及测试：https://github.com/yunyu950908/algorithms/blob/master/test/sort_merge.js

复杂度分析

看图，很浅显易懂的一张图，表示了递归的时间复杂度
在 O(logn) 的每一层都有一个合子数组的过程，该过程复杂度为O(n)

综上

时间复杂度：最好 O(nlogn)，最坏 O(nlogn)，平均 O(nlogn)
空间复杂度：申请存放子数组的临时空间 O(n)

大概就酱啦~ 还有不明白的或者是写错了的，欢迎交流纠正~
源码和测试在这里 https://github.com/yunyu950908/algorithms/blob/master/test/sort_merge.js

sort: insertion

插入排序

reference: https://visualgo.net/en/sorting
由于本宝宝是第一次学习，一边学习一边记录，难免会有错误，还请大佬指出，不胜感激~

排序说明

插入排序需要两个嵌套的循环。

外循环

外循环确定当前要进行排序元素的游标。(1)
外循环每次迭代，即有一个元素被交换到了 相对正确 的位置，移动游标到下一个要排序的元素。(4)
外循环结束，排序结束。(5)

内循环

内循环遍历从游标开始往前的每个元素；(2)
通过两两比较，如果前一个元素比它大，则交换位置，否则不动。(3)
内循环结束后，外循环移动游标到下一个要排序的元素，开始新一轮的内循环。(4)

�由上述说明，大致上一共有 5 个过程。

Tips: 插入排序每次只移动一个元素的位置, 不会改变同值元素之间的排序, 因此它是一种稳定排序。

代码实现

先贴上可视化学习资料：https://visualgo.net/en/sorting

以及右下角的伪代码

mark first element as sorted
for each unsorted element X
  'extract' the element X
  for j = lastSortedIndex down to 0
    if current element j > X
      move sorted element to the right by 1
    break loop and insert X here

第一版：
直接照着伪代码写成 JS

// swap 函数交换元素
function swap(a, b, array) {
  const temp = array[a];
  array[a] = array[b];
  array[b] = temp;
  return null;
}

// insertionSort
function insertionSort(array) {
  let lastSortedIndex = 0; // 最后一个已排序元素下标
  for (let i = 1; i < array.length; i++) { // 外循环遍历未排序元素
    const unsortedX = array[i]; // 存档当前外循环游标指定的未排序元素
    for (let j = lastSortedIndex; j >= 0; j--) { // 内循环遍历已排序元素
      if (array[j] > unsortedX) { // 如果已排序元素大于未排序元素，则交换位置
        swap(j, j + 1, array);
        array[j] = unsortedX;
      } else {
        break; // 否则代表已被交换到相对正确的位置，退出本轮内循环
      }
    }
    lastSortedIndex++; // 最后一个已排序元素下标 + 1
  }
  return array;
}

emmmm... 看起来是没啥问题哦...

复杂度分析

插入排序的复杂度分析

外循环：最好 O(n)，最坏 O(n)，
内循环：最好 O(1)，最坏 O(n)

所以结果应该是

时间复杂度：最好 O(n)，最坏 O(n²)，平均 O(n²)
空间复杂度：一个 swap temp 的临时交换空间，所以是 O(1)

大概就酱啦~ 代码应该写的很清楚了，还有不明白的或者是写错了的，欢迎交流纠正~
源码和测试在这里 https://github.com/yunyu950908/algorithms/blob/master/test/sort_insertion.js

yunyu950908 / algo Goto Github PK

algo's People

Contributors

Watchers

algo's Issues

目录

一、排序 SORT

队列

特性

队列的实现

Linked 双向链表

Queue 队列

队列的应用

选择排序

排序说明

代码实现

复杂度分析

链表

特性

定义链表

设计链表

试试性能

双向链表

循环链表

快速排序

排序说明

冒泡排序

排序说明

代码实现

复杂度分析

栈

特性

栈的实现

Linked 双向链表

Stack 栈

栈的应用

归并排序

排序说明

代码实现

复杂度分析

插入排序

排序说明

代码实现

复杂度分析

Recommend Projects

Recommend Topics

Recommend Org