cocos543/DSA

Data Structure & Algorithm, 算法之美, Go语言实现

DSA

Data Structure & Algorithm, 算法之美, Go语言实现

安装方法

go get github.com/cocos543/DSA
cd $GOPATH/src/github.com/cocos543/DSA/core && go run main.go

实现必修的数据结构与算法

单向链表

链表常见操作

• 反转单向链表 ✓

  时间复杂度O(n), 空间复杂度O(1)

• 链表中环的检测 ✓

  时间复杂度O(n), 空间复杂度O(1)

• 合并两个有序链表 ✓

  时间复杂度O(n), 空间复杂度O(1)

• 删除链表倒数第N个节点 ✓

  时间复杂度O(n), 空间复杂度O(1)

• 求链表的中间节点 ✓

  时间复杂度O(n), 空间复杂度O(1)

双向链表

栈

栈存储结构

• 顺序栈 ✓

• 链式栈 ✓

队列

• 顺序队列 ✓

排序

稳定的排序算法

• 冒泡排序 ✓

  最好时间复杂度O(n), 最坏时间复杂度O(n^2), 平均时间复杂度O(n^2), 空间复杂度O(1)

• 直接插入排序 ✓

  最好时间复杂度O(n), 最坏时间复杂度O(n^2), 平均时间复杂度O(n^2), 空间复杂度O(1)

• 计数排序(特殊桶排序) ✓

  时间复杂度O(n), 空间复杂度O(n)

• 归并排序 ✓

  最好时间复杂度O(nlogn), 最坏时间复杂度O(nlogn), 平均时间复杂度O(nlogn), 空间复杂度O(n)

不稳定的排序算法

• 快速排序 ✓

  最好时间复杂度O(nlogn), 最坏时间复杂度O(n^2), 平均时间复杂度O(nlogn), 空间复杂度O(1)

• 快排**查找第k大元素 ✓

  时间复杂度O(n), 空间复杂度O(1)

  分区函数算法示意图

查找

二分查找

• 二分查找 ✓

  时间复杂度O(logn), 空间复杂度O(1)

• 求解平方根 ✓

  时间复杂度O(logn), 空间复杂度O(1)

• 在循环数组中做二分查找 ✓

  时间复杂度O(logn), 空间复杂度O(1)

四种二分查找的变形算法

1. 查找第一个值等于给定值的元素 ✓

2. 查找最后一个值等于给定值的元素 ✓

3. 查找第一个大于等于给定值的元素 ✓

4. 查找最后一个小于等于给定值的元素 ✓