# 用Java实现算法和数据结构
本项目主要用于自己在工作之余记录用Java实现的算法和数据结构的源码;同时还会记录自己刷leetcode的题解思路等;
> Tip:如果读者电脑无法浏览到github图片,则需要设置hosts配置文件, 解决办法:
[解决方案](https://zhuanlan.zhihu.com/p/107691233)
# 经典排序算法
✅ [冒泡排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
✅ [选择排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
✅ [插入排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
✅ [插入排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
✅ [归并排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
✅ [快速排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
✅ [希尔排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
✅ [桶排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E6%A1%B6%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
✅ [基数排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
✅ [堆排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%A0%86%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
## 排序算法总结
| 排序名 | 平均时间复杂度 | 空间复杂度 | 优势 | 劣势 | 适用场景 | 稳定性 |
| :--: | :------: | :----------: | :--: | :--: | :-----------------------: | :--: |
| 冒泡排序 | O(n^2) | O(1) | | | | 稳定 |
| 插入排序 | O(n^2) | O(1) | | | | 稳定 |
| 计数排序 | O(n + k) | O(M) | | | 对于用例少的数据,比如对人的年龄排序或者身高排序。 | 稳定 |
| 基数排序 | O(d(n+r)) | O(M) | | | | 稳定 |
| 桶排序 | O(n+k) | O(n + k) | | | | 稳定 |
| 选择排序 | O(n^2) | O(1) | | | | 不稳定 |
| 归并排序 | O(nlogn) | O(N) | | | | 稳定 |
| 快速排序 | O(nlogn) | O(logn)~O(n) | | | | 不稳定 |
| 希尔排序 | O(nlogn) | O(1) | | | | 不稳定 |
| 堆排序 | O(nlogn) | O(1) | | | | 不稳定 |
## 其他算法总结
- 二分查找法,时间复杂度为O(logn)
## 其他
注意这里总结的都是平均时间复杂度。
例如插入排序,如果是有序的数组,则时间复杂度会退化成O(n)。而快速排序,对于每次选择的p位置都是末尾位置,则会退化成时间复杂度为O(n^2)(通过让p的位置随机来解决这个问题)。
对于归并排序、快速排序、堆排序这三个O(nlogn)的排序来说,时间复杂度是有常数级别的区别的,但是快速排序是相对更快的一种排序。
这里还需要注意的是,对于插入排序、快速排序、堆排序来说,都是原地排序的,即不需要额外的空间;而归并排序则是非原地排序,需要借助额外空间。
1. 排序算法的稳定性:对于相等的元素,在排序后,原来靠前的元素依然靠前,相等元素的相对位置没有发生改变。
2. 对于算法面试来说,除非面试题特别说明,否则认为要排序的数据范围是均匀分布的。
3. 快速排序之所以叫快速排序,并不代表它比堆排序和归并排序优良。在最好情况下,它的渐进复杂度与 堆排序和归并排序是相同的。知识快速排序的常量系数比较小而已。
4. 类库上提供的排序,并不是某一种算法的实现,而是综合了多种排序的综合排序。当数组比较小时,使用插入排序;当数组较大时,选择快速排序或其他的O(nlogn)的排序。
# 经典算法
KMP算法
马拉车算法
Prim算法
Krusk算法
Dijkstra算法
Bellman-Ford算法
# 经典数据结构
数组
栈和队列
链表
二分搜索树
集合和映射
✅ [堆和优先队列](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/datastructures/%E5%A0%86%E5%92%8C%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97.md)
线段树
Trie树
并查集
✅ [AVL树](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/datastructures/AVL%E6%A0%91.md)
红黑树
哈希表
# 数据结构总结
线性结构和非线性结构数据结构的区别
> 线性结构
1. 线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系。
2. 线性结构拥有两种不同的存储结构,即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的,链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。
3. 线性结构中存在两种操作受限的使用场景,即队列和栈。栈的操作只能在线性表的一端进行,就是我们常说的先进后出(FILO),队列的插入操作在线性表的一端进行而其他操作在线性表的另一端进行,先进先出(FIFO),由于线性结构存在两种存储结构,因 此队列和栈各存在两个实现方式。
4. 常见的线性结构包括:数组、链表、堆栈和队列等。
> 非线性结构
1. 树作为一种应用广泛的一对多非线性数据结构,不仅有数据间的指向关系,还有层级关系,常见的有二分搜索树(二叉树)、AVL树、B树以及红黑树等。
| 名称 | 类型 | 特性 | 常见应用 |
| :----: | :----: | :----: | :----: |
| 数组 | 线性结构 | 1. 基础数据机构;底层通过索引快速取得元素值;<br/> 2. 查询快O(1),增删慢O(n); | JDK中的ArrayList |
| 链表 | 线性结构 | 1. 以链表节点为元素,元素中包含指向下一节点的引用;<br/> 2. 链表分为单向链表和双向链表,区别在于双向链表有前驱节点和后继节点;<br/> 3. 查询慢O(n),增删快O(1);| JDK中的LinkedList、LinkedHashMap等 |
| 栈 | 线性结构 | 1. 先进后出的数据结构;| JDK中的SynchronousQueue |
| 队列 | 线性结构 | 1. 先进先出的数据结构;| JDK中的线程池底层的队列,包括:LinkedBlockingQueue、SynchronousQueue、ArraysBlockingQueue、DelayQueue等 |
| 二分搜索树 | 非线性结构 | 1. 二分搜索树是一颗二叉树,每棵树节点都包含了节点值;<br/> 2. 每个节点值都大于左子树的所有节点的值,而小于右子树的所有节点的值;<br/>| x |
| AVL树 | 非线性结构 | 1. AVL树是一个平衡二叉树,平衡二叉树的特性就是指左右加点的差值不能大于一;<br/> 2. AVL树每次插入、删除都需要进行左旋、右旋来保持AVL树的平衡性,因而这种维护需要更多代价; <br/> 3. AVL树的高度平衡,查找节点效率高;<br/> 4. AVL树的高度为logN;| windows对
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
用Java实现基础数据结构,排序算法、经典算法以及leetcode刷题记录_Java_下载.zip (96个子文件)
AlgorithmsInJava-master
pom.xml 831B
src
main
java
com
bruis
algorithminjava
utils
SortTestHelper.java 5KB
algorithm
sort
MergeSortBU.java 1KB
MergeSortAdvanced01.java 1KB
BinarySearch.java 671B
QuickSort2.java 2KB
QuickSort3Ways.java 1KB
HeapSort02.java 3KB
QuickSort2Ways.java 2KB
HeapSort01.java 2KB
QuickSort.java 1KB
BucketSort.java 2KB
ShellSort.java 605B
InsertionSort.java 2KB
BubbleSort.java 2KB
MergeSort.java 2KB
Heap.java 2KB
huawei
Question01.java 1KB
stack
MinStack.java 1KB
leetcode
ContainsDuplicate_217.java 3KB
LongestPalindromicSubstring_5.java 167B
array
IsPalindrome.java 1KB
ThreeSum.java 6KB
MaximumGap.java 5KB
SubarraySumEqualsK.java 3KB
ReverseVowels.java 1KB
SortColors.java 1KB
TopKFrequentElements.java 2KB
TwoSumII.java 868B
TwoSum.java 2KB
ReversePairs.java 5KB
MaximumProductSubarray.java 2KB
TwoSumII.java 1KB
TwoSum.java 2KB
MaximumSubarray_53.java 2KB
datastructures
array
MyArray.java 5KB
heap
MaxHeap.java 5KB
IndexMapHeap.java 6KB
stack
MyStack.java 2KB
Stack.java 226B
queue
Queue.java 283B
MyLoopQueue.java 3KB
MyQueue.java 2KB
notes
pictures
indexHeap03.jpg 37KB
heap04.png 76KB
heapSort02.gif 274KB
avl04.png 8KB
indexHeap02.jpg 34KB
avl10.png 10KB
1557906108-5066-20161218163120151-452283750.png 244KB
avl17.png 5KB
avl13.png 10KB
insertionSort.gif 360KB
avl11.png 9KB
heap03.png 84KB
avl12.png 12KB
avl09.png 8KB
avl08.png 5KB
heapSort01.gif 1.48MB
mergeSort.gif 326KB
avl06.png 12KB
avl01.png 9KB
avl18.png 5KB
indexHeap04.jpg 36KB
heap07.png 34KB
heap05.png 77KB
heap06.png 72KB
avl15.png 5KB
avl03.png 9KB
heap02.png 72KB
shellSort.gif 271KB
avl02.png 8KB
bubbleSort.gif 343KB
heap01.png 67KB
avl05.png 7KB
avl14.png 5KB
zan.jpg 29KB
quickSort.gif 270KB
avl07.png 8KB
avl16.png 5KB
indexHeap01.jpg 36KB
selectionSort.gif 459KB
algorithms
希尔排序算法.md 1KB
基数排序算法.md 0B
插入排序算法.md 2KB
冒泡排序算法.md 3KB
快速排序算法.md 8KB
基础排序算法.md 12KB
选择排序算法.md 1KB
桶排序算法.md 0B
堆排序算法.md 6KB
归并排序算法.md 2KB
datastructures
AVL树.md 15KB
堆和优先队列.md 19KB
test
.gitignore 334B
README.md 12KB
共 96 条
- 1
资源评论
m0_57781768
- 粉丝: 8963
- 资源: 403
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功