Skip to content

Instantly share code, notes, and snippets.

@fanfeilong

fanfeilong/datastruct and algorithm.md

Last active October 28, 2017 14:31
Show Gist options
  • Save fanfeilong/49682ae4fb562480b445 to your computer and use it in GitHub Desktop.
Save fanfeilong/49682ae4fb562480b445 to your computer and use it in GitHub Desktop.
Download ZIP
datastruct and algorithm
Raw
datastruct and algorithm.md

基本算法

  • 排序

    • 穩定的

      • 冒泡排序(bubble sort)-O(n^2)
      • 鸡尾酒排序(cocktail sort, 雙向的冒泡排序)-O(n^2)
      • 插入排序(insertion sort)-O(n^2)
      • 桶排序(bucket sort)-O(n);需要O(k)額外空間
      • 计数排序(counting sort)-O(n+k);需要O(n+k)額外空間
      • 归并排序(merge sort)-O(n*\log_{n});需要O(n)額外空間
      • 原地归并排序- O(n^2)
      • 二叉排序树排序(binary tree sort)- O(n*\log_{n})期望时间; O(n^2)最坏时间;需要O(n)額外空間
      • 鸽巢排序(pigeonhole sort)-O(n+k);需要O(k)額外空間
      • 基數排序(radix sort)-O(n+k);需要O(n)額外空間
      • 侏儒排序(gnome sort)- O(n^2)
      • 图书馆排序(library sort)- O(n*\log_{n}) with high probability, 需要(1+ε)n額外空間

    • 不穩定

      • 選擇排序(selection sort)-O(n^2)
      • 希爾排序(shell sort)-O(n*\log_{n})如果使用最佳的現在版本
      • 组合排序- O(n*\log_{n})
      • 堆排序(heap sort)-O(n*\log_{n})
      • 平滑排序(smooth sort)- O(n*\log_{n})
      • 快速排序(quick sort)-O(n*\log_{n})期望時間, O(n^2)最壞情況;對於大的、亂數串列一般相信是最快的已知排序
      • 內省排序(introsort)-O(n*\log_{n})
      • 耐心排序(patience sort)-O(n*\log_{n}+k)最坏情況時間，需要額外的O(n+k)空間，也需要找到最長的遞增子序列(longest increasing subsequence)

    • 不實用的排序算法

      • Bogo排序- O(n × n!)，最壞的情況下期望時間為無窮。
      • Stupid排序-O(n3);遞迴版本需要O(n^2)額外記憶體
      • 珠排序(bead sort)- O(n) or O(\sqrt_{n}), 但需要特別的硬體
      • Pancake sorting-O(n), 但需要特別的硬體
      • 臭皮匠排序(stooge sort)算法简单，但需要约n^2.7的时间

  • 查找

    • 线性查找
    • 二分查找

基本数据结构

  • 数组
  • 列表
  • 栈
  • 队列
  • 树
    • 二叉树
    • 多叉树
  • 字符串
    • 字符串相关算法
      • Naïve string search algorithm
      • Rabin–Karp string search algorithm
      • Finite-state automaton based search
      • Knuth–Morris–Pratt algorithm
      • Boyer–Moore string search algorithm
      • Bitap algorithm
      • Aho–Corasick string matching algorithm
      • Commentz-Walter algorithm
      • Rabin–Karp string search algorithm
      • regular expression
      • EXACT STRING MATCHING ALGORITHMS
  • 图
@fanfeilong
Copy link
Author

冒泡排序

function bubblesort(A)
  local swapped=false
  repeat
    swapped=false
    for i=1,#A-1 do
      if A[i]>A[i+1] then
        A[i],A[i+1]=A[i+1],A[i]
        swapped=true
      end
    end
  until not swapped
end

@fanfeilong
Copy link
Author

鸡尾酒排序

function cocktailsort(A)
  local swapped=false
  repeat
    swapped=false
    for i=1,#A-1 do
      if A[i]>A[i+1] then
        A[i],A[i+1]=A[i+1],A[i]
        swapped=true
      end
    end
    if not swapped then break end
    for i=#A-1,1,-1 do
      if A[i]>A[i+1] then
        A[i],A[i+1]=A[i+1],A[i]
        swapped=true
      end
    end
  until not swapped
end

@fanfeilong
Copy link
Author

插入排序

function insertsort(A)
  for i=2,#A-1 do
    local value=A[i]
    j=i-1
    while j>0 and A[j]>value do
      A[j+1]=A[j]
      j=j-1
    end
    A[j+1]=value
  end
end

@fanfeilong
Copy link
Author

桶排序

function buketsort(A,n)
  local bukets = {}
  for i=1,#A do
    table.insert(A,msbits(A[i],n),A[i])
  end
  for i=1,n do
    sort(bukets[i])
  end
  local result={}
  for i=1:n do
    result.contenation(result,bukets[i])
  end
  return result
end

@fanfeilong
Copy link
Author

RangeList题目

设Range是一个左闭右开区间 Range{int Begin;int End;},而RangeList是Range组成的有序集合。写一个函数Diff：

Diff(RangeList rangeList1,RangeList rangeList2, RangeList* leftOnly,RangeList* intersect,RangeList* rightOnly);

这个函数传入两个RangeList，返回三个RangeList，分别表示：只在第一个RangeList里面的部分，两个RangeList的交集部分，只在第二个RangeList里面的部分。

测试例子：
First:
[0,1000) [2000,4000) [5000,8000) [8001,8003)

Second:
[0,300) [500,3000) [3001,3500) [3600,4500)

结果如下：

left Only:
[300,500) [3000,3001) [3500,3600) [5000,8000) [8001,8003)

Intersect:
[0,300) [500,1000) [2000,3000) [3001,3500) [3600,4000)

Right Only:
[1000,2000) [4000,4500) [4000,4500)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment