文章目录

• 前言
• 一、数据结构
• • 概述
  • 结构
  • 线性数据结构
  • 非线性数据结构
  • 集合
  • 数据结构的比较和选择
  • • 常用数据结构
    • 数据结构选择
• 二、算法
• • 概述
  • 算法的5个特征
  • 二分查找算法
  • 排序算法实现
  • • 1.冒泡排序
    • 2.快速排序
    • 3.选择排序
    • 4.插入排序
    • 5.归并排序
    • 测试
• 总结

前言

数据结构与算法就是预估程序在大量的数据集上运行时需要的时间成本和空间成本！

一、数据结构

概述

 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

结构

 选择适当的数据结构可以提高计算机程序的运行效率（时间复杂度）和存储效率（空间复杂度）。

1. Data_Structure，它是储存数据的一种结构体，在此结构中储存一些数据，而这些数据之间有一定的关系。
2. 而各数据元素之间的相互关系，又包括三个组成成分，数据的逻辑结构，数据的物理结构和数据运算结构。
3. 而一个数据结构的设计过程分成抽象层、存储层和实现层。
   1. 逻辑结构——抽象层：主要描述的是数据元素之间的逻辑关系
   2. 物理结构——存储层：主要描述的是数据元素之间的位置关系
   3. 运算结构——实现层：主要描述的是如何实现数据结构

数据结构两大类：线性数据结构和非线性数据结构

线性数据结构

一维数组(Array)，链表(LinkedList)，栈(Stack)，队列(Queue)，串

1. 数组（Array）：它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。支持随机访问，只需要一个下标就可以访问到该元素。所以insert的的时候可以根据下标插入到具体的某个位置，但是这个时候它后面的元素都得往后面移动一位。所以插入效率比较低,更新，删除效率也比较低，而查询效率非常高,查询效率时间复杂度是1。Java里面常用的util有：String []，int []，ArrayList，Vector，CopyOnWriteArrayList等。
2. 链表（LinkedList）：虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据。插入效率比较高，插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了，如果实现的不好，需要整个链路找下去才能找到应该找的元素。
3. 栈（Stack）：是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈（push），取出元素叫出栈（pop）。
4. 队列（Queue）：是先进先出的线性表。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。不支持随机访问。只能从队尾添加元素（入队），只能从队首取出元素（出队）。队列又有单项有序队列，双向队列，阻塞队列等。
5. 串：也称字符串，是由N个字符组成的优先序列。在Java里面就是指 String ，而 String 里面是由 char[]来进行储存。

KMP算法：Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法。

KMP算法核心思想：是充分利用上次不匹配时的计算结果，避免"一切重新开始"的计算工作。

关键点就是：在字符串比对的时候，主串的比较位置不需要回退的问题。

非线性数据结构

二维数组，多维数组，树(Tree)，散列表(Hash)，图(Graph)

1. 二维数组和多维数组：无非就是String[][]，int[][]等
2. 树（Tree）：是由n（n>=1）个有限节点组成一个具有层次关系的集合。非排序树，主要用来做数据储存和展示。而排序树，主要用来做算法和运算，HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。

树的三种遍历方式

1. 先序遍历：根节点 → 左子树 → 右子树
2. 中序遍历：左子树 → 根节点 → 右子树
3. 后序遍历：左子树 → 右子树 → 根节点

自由树/普通树，二叉树，完全二叉树，满二叉树，二分搜索树，红黑树，B树，B+树

• 自由树/普通树：对子节点没有任何约束。
  
• 二叉树：每个节点最多含有两个子节点的树称为二叉树。
  
  • 一般二叉树：每个子节点的父亲节点不一定有两个子节点的二叉树成为一般二叉树。
  • 完全二叉树：除了树的最后一层节点不需是满的，其他的每一层从左到右都是满的，如果最后一层节点不是满的，那么要求左满右不满。堆（heap）是完全二叉树，通常用数组实现。
  • 满二叉树：除叶子节点外，每个节点都有两个孩子
    
• 二分搜索树：binary search tree，又称二叉排序树、二叉查找树。是有序的。如果不为空，那么其左子树节点的值都小于根节点的值；右子树节点的值都大于根节点的值。
  
• 红黑树：通过制定了一些红黑标记和左右旋转规则来保证二叉树平衡。
  • 根节点是黑色。
  • 每个节点或者是黑色，或者是红色。
  • 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
  • 如果一个节点是红色的，则它的子节点必须是黑色的。
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
    
• B tree/B-tree：又称B树、B-树。又叫平衡 (balance) 多路查找树。
  • 每个结点最多有M-1个key，并且以升序排列（比如图中的5,8,9，最多3个）
  • 每个结点最多能有M个子节点（5,8,9下最多有4个子节点）
  • 根结点至少有2个子节点（比如图中的二层的左右）
    
• B+tree：又称B+。是B-树的变体，也是一种多路搜索树。
  • B+树的叶子结点都会被连成一条链表。叶子本身按索引值的大小从小到大进行排序。即这条链表是 从小到大的。多了条链表方便范围查找数据。
  • B+树内部有两种结点，一种是索引结点，一种是叶子结点。
  • B+树的索引结点并不会保存记录，只用于索引。只存key不存value。
  • 非叶子节点的子树指针与关键字个数相同。
    

4. 散列表（Hash）：Hash叫散列或哈希，就是把任意长度的输入（又叫做预映射），变换成固定长度的输出，该输出就是散列值。一般通过Hash算法实现。所谓的Hash算法都是散列算法，把任意长度的输入，变换成固定长度的输出，该输出就是散列值（如：MD5,SHA1,加解密算法等）。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

   • hashCode：所有的class都会有默认Object.java里面的 hashCode 的方法，如果自己没有重写，默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。不同的对象，不同的值有可能计算出来的hashCode可能是一样的。
   • Hash表：数据存储方式是综合了数组和链表的数据结构。如：HashTable，HashMap。哈希表具有较快（常量级）的查询速度，及相对较快的增删速度，所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”，我们可以理解为“链表的数组”。

5. 图（Graph）：图形结构的数据元素是多对多的关系。

   1. 无向图
   2. 有向图
      

集合

是由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。

数据结构的比较和选择

比较

常用数据结构

数据结构选择

二、算法

概述

• 空间复杂度：一句来理解就是，此算法在规模为n的情况下额外消耗的储存空间。
• 时间复杂度：一句来理解就是，此算法在规模为n的情况下，一个算法中的语句执行次数称为语句频度或时间频度。
• 稳定性：主要是来描述算法，每次执行完，得到的结果都是一样的，但是可以不同的顺序输入，可能消耗的时间复杂度和空间复杂度不一样。

算法的5个特征

有穷性，确定性，可行性，有输入，有输出。

二分查找算法

折半查找又称为“二分查找“，算法复杂度为 nlog2n。查找的序列首先必须是有序的才能进行折半查找。

• 优点：比较次数少，查找速度快，平均性能好，占用系统内存较少。
• 缺点：要求待查表为有序表，且插入删除困难。

折半查找思路

 设有序顺序表｛a[0], a[1], ......, a[n-1]｝，先求出查找区间中间元素下标 mid，然后将该位置值 a[mid] 与要查找值 key 比较。

• 若key=a[mid]，则查找成功，返回下标；
• 若key<a[mid]，则要查找元素在mid左侧，缩小查找区间到表前半部分再进行折半查找；
• 若key>a[mid]，则要查找元素在mid右侧，缩小查找区间到表后半部分再进行折半查找。

过程示例

代码示例，两种方式（递归和非递归）

public class Test {
    //非递归
    public int binSearch(int a[], int low, int high, int key){
        while(low<=high){
            int mid=(low+high)/2;
            if(a[mid]==key)
                return mid;
            else if(key<a[mid])
                high=mid-1;
            else
                low=mid+1;
        }
        return -1;
    }
 
    //递归
    public int binRecSearch(int a[], int low, int high, int key){
        if(low<=high){
            int mid=(low+high)/2;
            if(a[mid]==key)
                return mid;
            else if(key<a[mid])
                return binRecSearch(a, low,mid-1, key);
            else
                return binRecSearch(a,mid+1, high, key);
        }
        else
            return -1;
    }
 
    //测试
    public static void main(String[] args){
        int[] a = { -36, -3, 5, 16, 24, 30, 78, 84, 345, 1004};
        Test test = new Test();
 
        //非递归
        int pos1=test.binSearch(a,0,a.length-1,-3);
        if(pos1!=-1)
            System.out.println("-3所在的位置下标是 "+pos1);
        else
            System.out.println("找不到该数字84！");
 
        //递归
        int pos2=test.binRecSearch(a,0,a.length-1,84);
        if(pos2!=-1)
            System.out.println("84所在的位置下标是 "+pos2);
        else
            System.out.println("找不到该数字84！");
    }
}

排序算法实现

1.冒泡排序

基本思想

 冒泡排序（Bubble Sort） 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

代码实现

/**
 * 冒泡排序：比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 */
private static void bubbleSort(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        for (int j = i+1; j < arr.length; j++) {
            if (arr[i] > arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

2.快速排序

基本思想

 快速排序（Quick Sort） 使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤：

1. 从数列中挑出一个元素，称为 ”基准”（pivot）。
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
   

代码实现

/**
 * 快速排序：从数列中挑出一个元素，称为“基准”，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
 */
private static void quickSort(int[] arr, int start, int end){
    //结束左右递归
    if (start < end){
        int base = arr[start];   //选第一个数为基准指
        int temp;               //记录临时中间值
        int i = start, j = end; //start最左，end最右
        do {
            while ((arr[i] < base) && (i < end))
                i++;
            while ((arr[j] > base) && (j > start))
                j--;
            if (i <= j){
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }while (i <= j);
        if (start < j)
            quickSort(arr, start, j);
        if (end > i)
            quickSort(arr, i, end);
    }
}

3.选择排序

基本思想

 是一种简单直观的排序方法，每次寻找序列中的最小值，然后放在最末尾的位置。

代码实现

/**
 * 选择排序：是一种简单直观的排序方法，每次寻找序列中的最小值，然后放在最末尾的位置。
 */
private static void selectSort(int[] arr){
    int temp;
    for (int i = 0; i < arr.length; i++) {
        int k = i;
        for (int j = arr.length-1; j > i; j--) {
            if (arr[j] < arr[k]) k = j;
        }
        temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
}

4.插入排序

基本思想

 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码实现

/**
 * 插入排序：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
      * 从第一个元素开始，该元素可以认为已经被排序
      * 取出下一个元素，在已经排序的元素序列中从后向前扫描  
      * 如果该元素（已排序）大于新元素，将该元素移到下一位置
      * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置  
      * 将新元素插入到该位置中
      * 重复步骤2
 */
private static void insertSort(int[] arr){
    int temp, j;
    for (int i = 1; i < arr.length; i++) {
        temp = arr[i];
        for (j = i; j > 0 && temp < arr[j-1]; j--)
            arr[j] = arr[j-1];
        arr[j] = temp;
    }
}

5.归并排序

基本思想

 归并排序是典型的分治算法，它不断地将某个数组分为两个部分，分别对左子数组与右子数组进行排序，然后将两个数组合并为新的有序数组。

代码实现

/**
 * 归并排序：是建立在归并操作上的一种有效的排序算法，归并是指将两个已经排序的序列合并成一个序列的操作
      * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
      * 设定两个指针，最初位置分别为两个已经排序序列的起始位置
      * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
      * 重复步骤3直到某一指针达到序列尾
      * 将另一序列剩下的所有元素直接复制到合并序列尾
 */
private static void mergeSort(int[] arr, int left, int right){
    int t = 1;// 每组元素个数
    int size = right - left + 1;
    while (t < size) {
        int s = t;// 本次循环每组元素个数
        t = 2 * s;
        int i = left;
        while (i + (t - 1) < size) {
            merge(arr, i, i + (s - 1), i + (t - 1));
            i += t;
        }
        if (i + (s - 1) < right)
            merge(arr, i, i + (s - 1), right);
    }
}

//归并算法实现
private static void merge(int[] data, int p, int q, int r) {
    int[] B = new int[data.length];
    int s = p;
    int t = q + 1;
    int k = p;
    while (s <= q && t <= r) {
        if (data[s] <= data[t]) {
            B[k] = data[s];
            s++;
        } else {
            B[k] = data[t];
            t++;
        }
        k++;
    }
    if (s == q + 1)
        B[k++] = data[t++];
    else
        B[k++] = data[s++];
    for (int i = p; i <= r; i++)
        data[i] = B[i];
}

测试

package com.mizhu;

import java.util.Arrays;


public class NumberSort {
    //调用
    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 1, 0, 8};
        System.out.println("排序前---");
        System.out.println(Arrays.toString(arr));

//        bubbleSort(arr);
//        quickSort(arr,0, arr.length-1);
//        selectSort(arr);
//        insertSort(arr);
//        mergeSort(arr,0, arr.length-1);

        System.out.println("排序后---");
        System.out.println(Arrays.toString(arr));
    }
}

总结

觉得有用记得支持一下！！！