# algorithm

**Repository Path**: xushj/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: algorithm test
- **Primary Language**: Unknown
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-07-27
- **Last Updated**: 2023-11-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# algorithm

### 一、介绍
algorithm test


### 二、查找

#### binary search 二分法查找

-   切木头

#### double pointer 双指针

-   两个数之和
-   三个数之和
-   存水问题

### 三、排序

#### 冒泡 

算法步驟

比较相邻的元素，如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的比价，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
针对所有的元素重复以上的步骤，除了数组最后已经排好序的数组；
重复步骤1~3，直到排序完成。

![2021-12-29冒泡排序](https://img-blog.csdnimg.cn/4ec14a4c6f524d63b6d78f6d914515a8.gif)

#### [选择](https://blog.csdn.net/qq_43794633/article/details/121612149) 
算法步驟
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
重复第2步，直到所有元素均排序完毕。

![2021-12-29选择排序](https://img-blog.csdnimg.cn/ab69a1575f6a449b8b3241a2a187b795.gif)

#### [插入](https://blog.csdn.net/weixin_60954394/article/details/121431922)

https://blog.csdn.net/qq_43794633/article/details/121612149 

①直接插入排序
基本思想
每次从一个有序序列开始，将待排元素与有序序列中的元素从后往前逐个比较，

若有序序列中的元素大于待排元素，则将较大的元素往后覆盖；

否则，将待排元素插入其前面，并结束此轮比较。

![2021-12-15_插入算法](https://img-blog.csdnimg.cn/8fbdd63675af47d2bdc134ea92dc6a2c.gif)
基本思想： gap = gap%3+1

将整个序列化分为间隔为3的子序列。

第一轮： 1 和 4 比较；2 和 5 比较； 3 和 6比较 ....
第二轮： 

#### 快排

算法步驟

1. 从序列中随机挑出一个元素，做为基准（pivot，这里选择序列的最左边元素作为基准）；
2. 重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面。该操作结束之后，该基准就处于数列的中间位置。这个操作称为分区（partition）；
3. 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行上述操作即可。

![2021-12-29快速排序](https://img-blog.csdnimg.cn/23e8959124464637b32145c8de36761d.gif)



#### 合并/归并排序
MergeSort

算法步骤：

1.如果待排序列只有一个元素，则直接返回，否则将长度为n的待排序列分成两个长度为n/2的子序列，递归进行调用进行分割知道每个子序列中只有一个元素；
此时的每个子序列被认为是有序的，然后递归调用的返回子序列进行两两合并；
2.合并过程中完成排序操作，具体操作为设定两个指针，分别指向两个已经排序子序列的起始位置；
3.比较两个指针所指向的元素，选择相对小的元素放入到合并返回的数组，并移动指针到下一位置；
4.重复步骤3~4直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾，最终得到的新序列就是有序序列。

![2021-12-29 归并排序](https://img-blog.csdnimg.cn/6a2626d8bdc24992aa750a54dbcbfc09.gif)

![2021-12-29 归并排序1](https://img-blog.csdnimg.cn/db030afdc9e84ff7ad1f11d15d3c9356.png)


#### [希尔排序](https://blog.csdn.net/weixin_37818081/article/details/79202115)


### 四、树

####  [二叉树的序列化与反序列化](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/)
 
#### 二叉树的遍历

#### 二叉树的前序遍历

#### 二叉树的中序遍历

#### [二叉树的后序遍历 traverse](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/submissions/)

#### [二叉树的右视角 rihtview](https://leetcode-cn.com/problems/binary-tree-right-side-view/)

#### [二叉树的最近公共祖先 lowest](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)

#### [判断一棵树是否为平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/)

给定一个二叉树，判断它是否是高度平衡的二叉树。

### 五、堆

#### 查找流中的中位数


### 六、Hash

#### [和为k的子数组](https://leetcode-cn.com/problems/QTMn0o/)
#### [克隆图](https://leetcode-cn.com/problems/clone-graph/)