# study.datastruct.algorithm

**Repository Path**: uyong/study.datastruct.algorithm

## Basic Information

- **Project Name**: study.datastruct.algorithm
- **Description**: 学习数据结构和算法过程中的代码示例
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2019-01-29
- **Last Updated**: 2022-07-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### 介绍
学习数据结构和算法过程中的代码示例


### 排序算法

#### 冒泡排序
时间复杂度：`O(n^2)`<br>
空间复杂度：`O(1)`<br>
稳定，原地
---

#### 插入排序
时间复杂度：`O(n^2)`<br>
空间复杂度：`O(1)`<br>
稳定，原地
---

#### 选择排序
时间复杂度：`O(n^2)`<br>
空间复杂度：`O(1)`<br>
不稳定，原地

>以上三种排序算法时间复杂度都是`O(n^2)`，适合**小规模数据**的排序。**插入排序**应作为首选，因为选择排序不稳定，冒泡排序交换时需要3个操作，插入排序移动时只需1个操作

---
#### 归并排序（分治思想）
时间复杂度：`O(nlogn)`<br>
空间复杂度：`O(n)`<br>
稳定，非原地
---

#### 快速排序（分治分区）
时间复杂度：`O(nlogn)`<br>
空间复杂度：`O(1)`<br>
不稳定，原地

>以上两种排序算法用的都是分治的思想，通过递归实现，需要注意*栈溢出*。快速排序用的比较广泛，虽然归并排序时间复杂度总是保持`O(nlogn)`，而快速排序最坏时间复杂度是`O(n^2)`，但快排空间复杂度低，且退化到`O(n^2)`的概率很小，可以通过合理的选择分区点来避免这种情况

---
#### 桶排序
>基本思想：根据数据的范围[min,max]分配一定数量的桶，每个桶存放桶范围内的数据，桶内的数据用其他排序算法，比如插入排序，最后依次输出每个桶内已排序的数据

时间复杂度：`O(n)`<br>
空间复杂度：`O(n)`<br>
稳定，非原地
>适用场景：外部排序（数据量很大，无法一次性加载到内存中）；桶数据分布比较均匀（极端情况，如果数据全被划分到一个桶里，则复杂度要看选择的桶内排序算法）

---
#### 计数排序
>基本思想：根据数据的范围[min,max]分配max-min个桶，每个桶对应一种数据的数量，对所有的计数累加（每一项为当前项和前面各项的和），最后根据计数算出数据在有序数组中的实际下标

时间复杂度：`O(n)`<br>
空间复杂度：`O(n)`<br>
稳定，非原地
>适用场景：数据范围不大（数据范围过大会消耗大量内存）；非负整数（保证大小不变的情况下可将负数转换为正整数）

---
#### 基数排序
>基本思想：将数据按位独立的分割出来做桶排序或者计数排序，这样要保证每个数据长度一样，不足的可以用填充。

时间复杂度：`O(n)`<br>
空间复杂度：`O(n)`<br>
稳定，非原地
>适用场景：数据可以按位分割，位之间有递进关系，比如英文单词和电话号码排序

---
### 查找算法

#### 二分查找
时间复杂度：`O(logn)`<br>
>适用场景：有序数组，因为二分查找依赖的是数组的随机访问特性

---

### 树
#### 二叉树
高度、深度、层<br>
前序遍历、中序遍历、后序遍历<br>
遍历时间复杂度：`O(n)`<br>
---
#### 二叉查找树
>定义：树中任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都要大于这个节点的值

>别名：二叉搜索树、二叉排序树

时间复杂度：查找、删除、插入：`O(logn)`，跟树的高度成正比

---

#### 红黑树
>红黑树是一种平衡二叉查找树，用于解决普通二叉查找树在频繁的动态插入、删除等操作下，出现时间复杂度退化到`O(n)`的问题。红黑树的高度近似log2n

时间复杂度：`O(logn)`

---
#### 堆
>定义：堆是一种特殊的树，满足两个条件：1.堆是一个完全二叉树；2.堆中的每一个节点的值大于等于（或小于等于）其子树的每个节点的值

时间复杂度：插入、删除：`O(logn)`，排序：`O(nlogn)`<br>
空间复杂度：`O(1)`<br>
排序：原地非稳定
>使用场景：优先级队列、求Top K和求中位数。虽然排序时间复杂度和快排一样，但常用的还是快排。

---

### 图
#### 深度优先算法
时间复杂度：`O(E)`，E为边数
空间复杂度：`O(V)`，V为顶点数

---
#### 广度优先算法
时间复杂度：`O(E)`，E为边数
空间复杂度：`O(V)`，V为顶点数
---

####