08_算法和数据结构

一、排序

1.冒泡排序

算法：

1. 整个数列分成两个部分，前面是无序数列，后面是有序数列
2. 初始状态下，整个数列都是无序的，有序数列是空的
3. 如果一个数列有n个元素，则最多需要n-1轮循环才能保证数列有序
4. 每一轮循环可以让无序数列中最大数排到最后
5. 每一轮循环都从数列第一个元素开始比较，一次比较相邻的两个元素，比较到无序数列的末尾停止（而不是数列的末尾）

6. 如果前一个大于后一个则进行交换

   public class Bubblesort {
    public static void main(String[] args) {
        int[] arr={45,23,67,11,34,88,14};
        boolean flag=true;
        for (int i = 0; i < arr.length-1; i++) {//比较的次数为数字元素个数减1
            for (int j = 0; j <arr.length-i-1 ; j++) {
                if (arr[j]>arr[j+1]){
                    int a=arr[j];//若是前者大于后者则进行数据交换，a为中间变量
                    arr[j]=arr[j+1];
                    arr[j+1]=a;
                    flag=false;
                }
                if (flag){//如果flag的值为true则证明没有进行比较，数组为有序的升序
                    System.out.println("数组排序结束");
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
   }

   2.选择排序

   选择排序的算法：

7. 整个数列分为两个部分：前面是有序数列，后面是无序数列

8. 初始状态下，整个数列都是无序的，有序数列是空的
9. 一共是n个数字，至少需要n-1轮的比较
10. 每比较一轮，有序数列数量+1，无序数列数量-1
11. 每轮先假设无序数列的第1个元素是最小的（也就是i），让当前的最小数从i+1的位置开始比较，遇到比第一个元素小的元素，赋值给索引标记变量index，然后让下标为index的元素继续与后边的元素做比较，一直比较到最后。

12. 将比较后下标为index的最小的元素赋值给索引为i的元素，索引为index的元素赋值为i的初始索引对应的值。

    public class SelectSort {
     public static void main(String[] args) {
         int[] arr={45,23,67,11,34,88,14};
         for (int i = 0; i <arr.length-1 ; i++) {//比较次数为总数减一
             int index=i;//假设index存放最小数的索引
             for (int j = i+1; j <arr.length ; j++) {
                 if (arr[index]>arr[j]){
                     index=j;
                 }
             }
             if (index!=i){//若index不等于i则证明找到了更小的数字
                 int a=arr[i];
                 arr[i]=arr[index];
                 arr[index]=a;
             }
         }
         System.out.println(Arrays.toString(arr));
     }
    }
    

    二、递归

13. 递归问题的特点：

一个问题可以被分解成若干层简单的子问题
子问题和其上层问题的解决方案一致
外层问题的解决依赖于子问题的解决

1. 递归结构
2. 优点：思路自然，程序简单
3. 缺点：递归调用会占用大量的系统堆栈，内存消耗多；且递归调用层次多时速度比循环慢很多。任何用递归解决的问题都可以替代为循环。

   1.求阶乘

   public class Factorial {
    public static void main(String[] args) {
        System.out.println(jc(5));
    }
    static  int jc(int a){
        if (a==1){
            return 1;
        }else{
            return a*jc(a-1);
        }
    }
   }
   

   2.斐波那契数列

   //斐波那契数列 1 1 2 3 5 8 13 21 34
   public class FactorialA {
    public static void main(String[] args) {
        System.out.println(aa(7));
    }
    static int aa(int a){
        if (a==1 || a==2){//停止条件
            return 1;
        }else{
            return  aa(a-1)+aa(a-2);
        }
    }
   }
   

3.循环实现二分查找

二分查找（折半查找），使用这种查找方法需要让待查表满足以下两个条件。 ```java public class Binary { public static void main(String[] args) { int[] arr={3,23,45,65,76,77,88,95,123}; int key=95; System.out.println(cz(arr,key)); } public static int cz(int[] arr,int key){ if (arr.length==0 || arr==null){ return -1; } int startindex=0; //起始位置 int endindex=arr.length-1; //中止位置 int middle; //中间位置 while (startindex<=endindex){ middle=(startindex+endindex)/2; if (key>arr[middle]){ startindex=middle+1; }else if (key<arr[middle]){ endindex=middle-1; }else{ return middle; } }

<a name="qAQ8R"></a>
### 4.递归实现二分查找
```java
public class BinaryB {
    public static void main(String[] args) {
        int[] arr={3,23,45,65,76,77,88,95,123};
        int key=95;
        int start=0;
        int end=arr.length-1;
        System.out.println(cz(arr,key,start,end));
    }
    public static int cz(int[]arr,int key,int start,int end){
            int middle=(start+end)/2;
            if (start>end){
                return -1;
            }
            if (key>arr[middle]){
                return cz(arr,key,middle+1,end);
            }else if (key<arr[middle]){
                return cz(arr,key,start,middle-1);
            }else {
                return middle;
            }
        }
}

三、数据结构

数据结构是指相互间存在一种或者多种特定关系的数据元素的集合。是组织并存储数据以便能够有效使用的一种专门的格式，用来反映一个数据内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。
数据结构=逻辑结构+存储结构+在存储结构上的运算或操作
运算的实现依赖于存储结构，逻辑结构唯一，但是物理存储结构不唯一

1.存储结构

顺序存储结构：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现：
链式存储结构：数据元素的存储对应的是不连续的存储空间，每个存储节点对应于一个需要存储的数据元素。每个结点是由数据域和指针域组成的。元素之间的逻辑关系通过存储节点之间的链接关系反应。逻辑上相邻节点物理上不必相邻。
索引存储结构：除建立存储节点信息外，还建立附加的索引来表示结点的地址。比如图书，字典的目录。
散列存储结构：根据结点的关键字直接计算出该节点的存储地址，比如java中的hashset，hashmap底层就是散列存储结构。这种结构添加、查询速度快。
同一逻辑结构可以对应多种存储结构
同样的运算在不同的存储结构中，其实现过程也是不同的

2.逻辑结构

线性结构：有且只有一个开始结点和终端结点，并且所有结点都是最多只有一个直接前驱和一个直接后继。

2.1线性表

特点：相同数据类型、序列（顺序性）、有限
集合中必存在唯一的一个“第一个元素”
集合中必存在唯一的一个“最后的元素”
除最后元素之外，其他数据元素均有唯一的“直接后继”
除第一元素之外，其他数据元素均有唯一的“直接前驱”
线性结构：数据元素之间存在着“一对一”的线性关系的数据结构
树状结构：除了一个数据元素以外每个数据元素有且只有一个直接前驱元素，但是可以有多个直接后续元素。如：文件系统
网络结构：每个数据元素可以有很多个直接前驱元素，也可以有多个直接后续元素。特点是数据元素之间是多对多的联系。如：交通线路图，地铁图
线性表逻辑结构对应的顺序存储结构为顺序表，对应的链式存储结构为链表。

2.2链表

单链表：数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。逻辑上相邻的节点物理上不必相邻
缺点：
1、比顺序存储结构的存储密度小。
2、查找结点时链式存储要比顺序存储慢
优点：
1、插入、删除灵活
2、有元素才会分配结点空间，不会有闲置的结点。
在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的最前面添加一个哑元结点，也称为头结点。 在头结点中不存储任何实质的数据对象，其 next 域指向线性表中0 号元素所在的结点， 可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。

双向链表：在双向链表中同样需要完成数据元素的查找、插入、删除等操作。在双向链表中进行查找与在单链表中类似，只不过在双向链表中查找操作可以从链表的首结点开始，也可以从尾结点开始，但是需要的时间和在单链表中一样。Java中的LinkedList底层使用的就是双向链表。
循环链表：在一个循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要遍历一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。循环链表可以被视为”无头无尾”。

2.3顺序表

顺序表特点：在内存中分配连续的空间，只存储数据，不需要存储地址信息。位置就隐含着地址。
优点：节省存储空间，索引查找效率高

缺点：插入和删除操作需要移动大量元素，效率低
必须提前分配固定数量的空间，如果存储元素少，可能导致空闲浪费
按照内容查询效率低，因为需要逐个判断

四、数据结构B

1.栈和队列

1.1栈

栈（stack ）又称堆栈，它是运算受限的线性表。其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为 栈顶（top），栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈底（bottom） 先进后出
当栈中没有数据元素时称为空栈。

1.2队列

队列（queue）简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
双端队列是指两端都可以进行进队和出队操作的队列，如下图所示，将队列的两端分别称为前端和后端，两端都可以入队和出队。其元素的逻辑结构仍是线性结构。其实包含输出受限的双端队列和输入受限的双端队列。

2.树

树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。树（tree ）是 n（n ≥ 0）个结点的有限集。

2.1二叉树

二叉树：
每个结点的度均不超过 2 的有序树，称为 二叉树（binary tree） 。二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称为根的左子树和右子树的子树所组成的非空树。
满二叉树：
高度为k并且有 2-1 个结点的二叉树。
满二叉树中，每层结点都达到最大数，即每层结点都是满的，因此称为满二叉树。
完全二叉树：
若在一棵满二叉树中，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树即为完全二叉树。
满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树
二叉树的存储结构
二叉树存储结构有两种：顺序存储结构和链式存储结构。更多使用链式存储结构

2.2查找树

二叉查找/搜索/排序树 BST (binary search/sort tree)
或者是一棵空树；
或者是具有下列性质的二叉树：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；
（2）若它的右子树上所有结点的值均大于它的根节点的值；
（3）它的左、右子树也分别为二叉排序树。
平衡二叉树（Self-balancing binary search tree） 自平衡二叉查找树 又被称为AVL树（有别于AVL算法）
平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度
平衡二叉树的常用实现方法有AVL、红黑树、替罪羊树、Treap、伸展树等

2.3红黑树

红黑树
R-B Tree，全称是Red-Black Tree，又称为”红黑树”，它一种平衡二叉树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(logN)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的

2.3区别

1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

3.图

图的基本概念：多对多关系
图（graph）是一种网状数据结构，图是由非空顶点集合和一个描述顶点间关系的集合组成。

3.1有向图

若∈E，则表示从顶点 u 到顶点 v 的一条弧，并称 u 为弧尾或起始点，称v 为弧头或终止点，此时图中顶点之间的连线是有方向的。