# algorithm

**Repository Path**: hucy001/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: BSD-3-Clause-Clear
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-07-22
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# algorithm
#### 选择排序
1. 找出数组中最小的元素，然后跟第一个元素交换位置。
2. 从剩下的元素找出最小的元素，然后跟第二个元素交换位置。
3. 如此往复，直到将整个数组排序。
4. 时间复杂度 N^2, 空间复杂度 1, 稳定性 否

#### 插入排序
1. 第n个元素的处理：假设前面n-1个元素有序，
2. 第n-1个元素和第n个元素比较，如果违反升序或降序，将第n-1个元素后移
3. 第n-2个元素和第n个元素比较，如果违反升序或降序，将第n-2个元素后移
4. 如此往复，直到第m个元素和第n个元素没有违反升序或降序，将第n个元素插入第m个元素后面（m<n）。
5. 如此往复，直到将整个数组排序。
6. 时间复杂度 N^2, 空间复杂度 1，稳定性 是

#### 希尔排序
1. 计算一个增量值gap：第一次 gap= len(N); 从第二次开始gap = gap/2
2. 从第gap个元素到最后一个元素遍历，每个元素做插入排序（相邻的元素相隔gap距离），例如 第i个元素和第i-gap个元素比较和移动。
3. 步骤1和2，如此往复，直到gap=1，执行最后一次插入排序，就完成了所有排序。
4. 增量序列算法：
- Hibbard增量序列的取法为Dk=2^k−1：{1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191...}
    - 最坏时间复杂度为O(N^3/2)；平均时间复杂度约为O(N^5/4)
- Sedgewick增量序列的取法为D=9∗4i−9∗2i+1或4i−3∗2i+1：{1, 5, 19, 41, 109, 209, 505, 929, 2161...}
    - 最坏时间复杂度为O(N^4/3)；平均时间复杂度约为O(N^7/6)
- Knuth增量序列的取法为Dk=3*k+1：{4,7,10...}
5. 时间复杂度 跟增量序列算法相关, 空间复杂度 1，稳定性 否

#### 归并排序 
1. 使用递归将源数列使用二分法分成多个子列：直到单个子列只有一个元素。
2. 将两个子列排序合并然后返回：
- 原地归并：
    1. 左边子列 a[0]...a[j0-1],右边子列 a[j0]...a[max]
    2. 向右移动左边元素位置i，直到a[i]>a[j0],得到元素子列 a[i]...a[j0-1]
    3. 向右移动右边元素位置j，直到a[i]<a[j1],得到元素子列 a[j0]...a[j1]
    4. 逆转元素子列 a[i]...a[j0-1]，得到a[j0-1]...a[i]
    5. 逆转元素子列 a[j0]...a[j1]，得到a[j1]...a[j0]
    6. 逆转元素子列 a[i]...a[j1]，得到a[j1]...a[i]
    7. 移动左边元素位置i，直到位置i+(j1-j0)
    8. 如此往复，直到条件不再成立：i<j&&j<=max
    9. 时间复杂度 nlogn, 空间复杂度 1
- 自顶向下：递归算法
- 自底向上：迭代算法
3. 时间复杂度 nlogn, 空间复杂度 n或者1，稳定性 是

#### 快速排序
1. 根据第一个元素a[0]，将数组切分成左右两个子列，左子列元素小于a[0],右子列元素大于a[0]
2. 左子列递归
3. 右子列递归
4. 算法改进
    - 切换到插入排序：数组的规模在15以内时，采用插入排序
    - 三取样切分：
        - 使用子数组的一小部分元素的中位数来切分数组，采样大小为3效果比较好
        - 将取样元素放在数组末尾，去掉partition()的数组边界测试
    - 熵最优的排序
        1. 解决大量重复元素的排序效率
        2. 三向切分快速排序：小于，等于，大于
5.  时间复杂度 （n - nlogn）, 空间复杂度 nlogn，稳定性 否

#### 优先队列
1. 初级实现
    1. 数组实现（无序）
    2. 数组实现（有序）
    3. 链表表示法
2. 堆定义
    1. a[k]的父节点为a[k/2]
    2. a[k]的左孩子为a[2k]，a[k]的右孩子为a[2k+1]
3. 堆算法
    1. 由下至上的堆有序化（上浮）：如果当前节点比父节点大，交换两者顺序，如此往复，直到当前节点小于或等于父节点
    2. 由上至下的堆有序化（下沉）：如果孩子节点比当前节点大，取孩子节点最大者与当前节点交换，如此往复，直到当前节点大于孩子节点
    3. 多叉堆
    4. 索引优先队列
        - 多向归并问题:
            1. 将大文件切分成多个小文件，对每个小文件做快速排序。 假如分成1000个文件，每个数据mod 1000.
            2. 利用最小索引优先队列，对所有的小文件排序。
4. 堆排序
    1. 堆的构造
		- 选择第1个元素k，k=n/2
		- 找出元素k的最大孩子节点
		- 如果元素k比最大孩子节点大，将元素k下沉（交换两者位置）
		- 如果发生交换，继续检查交换后的孩子节点是否需要下沉，直到最后一个孩子节点
		- 更新元素k的位置 k=k-1,并重复上面的步骤直到k=0
		- 堆构造完成后，父节点一定比所有子孙节点大。
    2. 下沉排序
    	- 先上浮后下沉
    	- 选择第k个元素，k=N
    	- 交换第1个元素和第k个元素
    	- 交换后，第k个元素值就是最大的
    	- 交换后，将第1个元素下沉
    	- 更新元素k的位置 k=k-1，并重复上面两步，直到k=1
    	- 下沉排序完成后，就得到了有序的最小堆
	3. 先下沉后上浮
		- 一种改进算法
		- 优点 将比较次数减半并接近归并排序所需的次数
		- 缺点 需要额外的空间
		- 实际应用场景 比较操作代价较高时
    ![iavatar](https://algs4.cs.princeton.edu/24pq/images/heapsort-trace.png)
    ![iavatar](https://algs4.cs.princeton.edu/24pq/images/heapsort.png)
5. 应用
	1. 将各种数据排序
	2. 选择合适的算法
		大多数情况下，快速排序是最佳选择。当然也有例外，如果稳定性重要而空间不是问题，归并排序可能是最好的。
        - 将原始数据类型排序
        - java系统库的排序算法
          java程序员选择对原始数据类型使用（三向切分的）快速排序，对引用类型数据使用归并排序
          这些选择暗示着用速度和空间（原始类型）来换取稳定性（引用类型）
        ![iavatar](https://algs4.cs.princeton.edu/25applications/images/sort-characteristics.png)
	3. 问题的归约
		- 归约是指为解决某个问题发明的算法正好可以用来解决另一种问题。
		- 找出重复元素
		- 排名：两个排列的kendall tau距离，社会学，分子生物学，搜索引擎
		- 优先队列
		- 中位数和顺序统计：优先队列或快速排序
	4. 排序应用一览
		- 商业计算，信息搜索，运筹学，事件驱动模拟，数值计算，组合搜索（图检索，霍夫曼压缩，字符串处理）

# 查找
#### 符号表
|使用的数据结构| 实现 | 优点 |缺点 |
| :------| :------: | :------ |:------ |
| 链表（顺序查找） | sequentialSearchST | 适用小型问题 |对于大型符号表很慢 |
| 有序数组（二分<br>查找) | BinarySearchST | 最优的查找效率和空间需<br>求，能够进行有序性相关<br>的操作 |插入操作很慢 |
| 二叉查找树 | BST | 实现简单，能够进行有序<br>性相关的操作 |没有性能上界的保证<br>链接需要额外的空间 |
| 平衡二叉树 | RedBlackBST | 最优的查找和插入效率，能<br>够进行有序性相关的操作 |链接需要额外的空间 |
| 散列表 | SeparateChainHashST | 能够快速查找和插入常<br>见类型的数据 |需要计算数据的散列无法进行有序性相<br>关的操作链接和空节点需要额外的空间 |
| 散列表 | LinearProbingHashST | 同上 |同上 |


#### 二叉查找树 
#### 平衡查找树
#### 哈希表
#### 查找应用



#### 参考资料
[https://algs4.cs.princeton.edu/home/](https://algs4.cs.princeton.edu/home/)  
[https://blog.csdn.net/u014044812/article/details/88764311](https://blog.csdn.net/u014044812/article/details/88764311)  
[https://www.cnblogs.com/wuxiangli/p/6399266.html](https://www.cnblogs.com/wuxiangli/p/6399266.html)