# DataStructuresAndAlgorithms

**Repository Path**: jeff_sunbaojin/DataStructuresAndAlgorithms

## Basic Information

- **Project Name**: DataStructuresAndAlgorithms
- **Description**: No description available
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2020-05-20
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

```text
访问github比较慢的解决方法：https://www.cnblogs.com/knuzy/p/9415243.html
结论，修改hosts，增加：
#github
199.232.69.194   github.global.ssl.fastly.net
140.82.113.4  github.com
199.232.68.133 avatars1.githubusercontent.com
```

# 数据结构和算法
## 1、稀疏数组[com.atguigu.datastructures.sparseArray]
* 完成11*11的数值转化为稀疏数组
```java
 /**
         * 转换为稀疏数组,思路：
         * 1.获取有效数值的个数sum
         * 2.创建一个int[sum+1][3]
         * 3.int[0]:存储 数值行数、列数、有效数值个数
         * 4.int[x]:存储有效数值的所在行、所在列，及其有效值
         */
```
* 完成稀疏数组转化为11*11原始数组
```java
        /**
         * 稀疏数组转换为原始数组思路
         * 1.根据稀疏数组的第一行获取行、列，创建数值
         * 2.从1开始循环，设置数值的值
         */
```
* 完成稀疏数组写入到本地磁盘文件
* 完成本地磁盘文件转化为稀疏数组
```java
 /**
         *写入磁盘思路
         * 1.将稀疏数组转化为 json字符串，存入文件
         * 2.读取文件，转化为稀疏数组
         * 3.将稀疏数组转化为原始数组
         */
```
*  总结：如果二维数组的总个数/3 > 二维数组的有效值个数，就不应该转换为稀疏数组了，
           因为 二维数组的有效值个数*3后，就会大于二维数组的总个数! 

## 2、队列-数组实现队列[com.atguigu.datastructures.QueueArrayMain]
* 完成固定位数的数组 com.atguigu.datastructures.QueueArray
```java
/**
 * 内部类，完成数组，属性如下
 * 1.maxSize:存储队列的最大容量
 * 2.front:存储队列的队首元素，不存在时，默认为-1；
 * 取出时，front ++
 * 3.rear:存储队列的队尾下标，不存在时，默认为-1；
 * *   增加时，rear ++
 * 4.arry[]:存储队列的元素
 */
```
* 按照自己的想法完成的环形数组 com.atguigu.datastructures.QueueAnnularArray
```java

/**
 * 个人思路(达到环形数组队列)：
 * 1) 判断数组是否满了/空了，思路如下：增加一个变量intCount，记录当前元素个数，
 * 如果intConut ==maxSize,认为满了；
 * 如果intConut == 0 ,认为空了；
 * 2）队尾rear:记录当前插入的节点的下标到哪了
 * 3) 队首front：记录当前取出的节点的下标到哪了
 * 3）增加一个当前下标的值nowIndex：记录队首
 * 4)改造方法参考【QueueAnnularArray】
 */
```
* 按照老师的取模思路完成的环形数组 com.atguigu.datastructures.QueueModuolArray
```java
/**
 * 用取模的思路进行解题：
 * 1.队首front含义做个调整：
 *   存储的就是当前元素的下标值，即arry[front] 就是当前的值，初始值就是0
 *   取出时，所以他对应数组的下标值计算公式为：
 *  index =  front %maxSize
 * 2.队尾rear含义做个调整：
 *   存储的就是下一个将要放进去的元素的下标值，初始值就是0；
 *   由于考虑到他一直会自增，所以他对应数组的下标值计算公式为：
 *     index = (rear +1) %maxSize
 * 3、判断满的条件，调整为：  (rear +1) %maxSize == front，说明就是满了
 * 4、判断空的条件，还是：  rear == front，说明就重合了
 * 5、判断有效个数：(rear + 1 - front)%maxSize  有效数组的个数肯定不会超过数组的长度！
 *
 * 重要：有个约定空间得概念，所以存储的最大元素数量为maxSzie -1
 *
 */
```
* 总结： 刚开始自己比较懵，还是需要多学习！！！有些地方还是想不明白！

## 3、链表
* 1.简单的无序列表[com.atguigu.datastructures.linkedlist.SimpleLinkedListMain]
    链表特点：包括2个区域、a、data域 b、next域
    一个头部根节点，插入时一定要找到最后一个节点的next为空，插入
* 2.单向链表的增删改查、反转、合并操作
* 3.双向链表的增删改查、反转、合并操作
* 4.单向环形链表的增删改查、反转、合并操作


## 4、栈
* 1.栈的原理：先进后出
* 2.栈实现中缀表达式的计算器
* 3.栈实现前缀表达式的计算器
* 4.栈实现后缀表达式的计算器
* 5.前缀、中缀、后缀表达式的相互转换

## 5、递归
* 1.递归的应用场景
* 2.递归的注意点：必须要尽可能的接近退出条件
* 3.递归实现迷宫问题
* 4.递归实现8皇后的问题解法，92种方法


## 6、排序
* 1.时间频次、时间复杂度的含义
```text
时间频度
基本介绍
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。[举例说明]
```
```text
时间复杂度

一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) )  为算法的渐进时间复杂度，简称时间复杂度。

T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。
计算时间复杂度的方法：

用常数1代替运行时间中的所有加法常数  T(n)=n²+7n+6  => T(n)=n²+7n+1
修改后的运行次数函数中，只保留最高阶项  T(n)=n²+7n+1 => T(n) = n²
去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)

常见的时间复杂度

常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(nlog2n)
平方阶O(n^2)
立方阶O(n^3)
k次方阶O(n^k)
指数阶O(2^n)

说明：
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低
从图中可见，我们应该尽可能避免使用指数阶的算法

```
* 2.冒泡排序
```text
基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待
排序序列从前向后（从下标较小的元素开始）,依次比较
相邻元素的值，若发现逆序则交换，使值较大
的元素逐渐从前移向后部，就象水底下的气泡一样逐渐
向上冒。

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下
来没有进行过交换，就说明序列有序，因此要在排序过程中设置
一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)

```
* 3.选择排序
```text
基本介绍

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

选择排序思想:

选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

```
* 4.插入排序
```text
插入排序法介绍:

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

插入排序法思想:

插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
```

* 5.希尔排序
```text
希尔排序法介绍

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

希尔排序法基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

```
* 6.快递排序
```text
快速排序法介绍:

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列


PS:空间换时间，用到了递归，但是效率很高，8000000，也就用了2s
```
* 7.基数排序
```text
基数排序(桶排序)介绍:

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用

基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法

基数排序(Radix Sort)是桶排序的扩展

基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序基本思想

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤

PS:典型的空间换时间，10个桶，那就扩大了10倍空间

```

## 7、查找
* 1.线性查找
```text
循环数组，查询值
```

* 2.二分查找
```text
1.数值必须有序的
2.先找数值下标为中间的值，和要查找的值进行比较
3.查找的值 》 中间的值，那就向右递归查找
4.查找的值 < 中间的值，那就向左递归查找
5.查找的值 == 中间的值，那就直接返回
```