/javascript-datastructures-algorithms

Primary LanguageJavaScript

Learning JavaScript Data Structures and Algorithms

Base

  • 数组 (Array)

  • 栈 (Stack)

  • 队列 (Queue)

  • 链表 (LinkedList)

    • 单链表 (LinkedList)
    • 双链表 (DoublyLinkedList)
    • 循环链表 (CircularLinkedList)
    • 判断链表是否成环 (LinkedListWithCycle)
    • 链表插入排序 (InsertionSort)
    • 链表快速排序 (QuickSort)
    • 链表归并排序 (MergeSort)

  • 集合 (Set)

  • 映射表(Map)

    • 字典 (Dictionary)
    • 散列表 (HashTable)
      • 分离链接 (HashCollisionSeparateChaining)
      • 线性探查 (HashCollisionLinearProbing)

TopK

  • 找第 k 大的元素 (Quick_Select)
  • 找最大的 k 个元素 (Heap)
  • 优先队列 (PriorityQueue)

Sort

  • 排序算法 (SortingAlgorithm)
    • 冒泡排序 (bubbleSort)
    • 选择排序 (selectionSort)
    • 插入排序 (insertionSort)
    • 归并排序 (mergeSort)
    • 快速排序 (quickSort)
    • 堆排序 (heapSort)
    • 希尔排序 (shellSort)
    • 计数排序 (countingSort)
    • 桶排序 (bucketSort)
    • 基数排序（分布式排序） (radixSort)

String

  • 字符串匹配 (KMP)

Tree

  • 二叉搜索树 (BinarySearchTree)
  • 迭代先序遍历、中序遍历、后序遍历 (OrderTraverse)
  • AVL树 (AVLTree)
    1. BST 的扩展
    2. 自平衡，任意节点的左右子树高度最多相差 1
    3. 插入和移除节点性能并不总是最好的（虽然自平衡），更好的选择是红黑树
  • 红黑树 (RedBlackTree)
    1. 可高效率有序地遍历其节点

Graph

  • 最短路 (ShortestPath)
    • dijkstra
    • floydWarshall
  • 最小生成树 (MinimumSpanningTree)
    • prim
    • kruskal

TODO

  • 优先队列 (PriorityQueue)
  • AVL树 (AVLTree)
  • 红黑树 (RedBlackTree)