「Java教程」数据结构与算法入门

Posted on | In

数据结构，它是储存数据的一种结构体，在此结构中储存一些数据，而这些数据之间有一定的关系。
算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或者多个操作。

1.Java数据结构(Data Structure)

1.1 数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
而各数据元素之间的相互关系，又包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。
而一个数据结构的设计过程分成抽象层、数据结构层和实现层。

1.2 Java数据结构

  • 数据结构在Java的语言体系中按数据的逻辑结构可以分为两大类：线性数据结构和非线性数据结构。
    1. 线性数据结构：常见的有：一维数组，线性表，栈，队列，双队列，串。
    2. 非线性数据结构：常见的有：多维数组，集合，树，图，散列表(hash)。
  • 按数据的存储结构分为：顺序存储结构和链式存储结构
    1. 顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
    2. 链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。

1.3 线性数据结构

常见的线性数据结构有：一维数组，线性表，栈，队列，双队列，串。

1.3.1 一维数组

数组是根据下标进行操作的，insert根据下标插入到具体位置，它后面的元素都往后面移动一位。

  • 插入/更新/删除效率比较低，而查询效率非常高; 查询效率时间复杂度是1。
  • Java中: String [],int [],ArrayList,Vector,CopyOnWriteArrayList等
1.3.2 线性表

线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的，链表的每一个节点都知道上一个节点、或者下一个节点是谁，通常用Node表示。
常见的方法有：add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。

  • 插入效率比较高，插入的时候只需要改变节点的前后节点的连接即可; 而查询效率就比较低。
  • Java中: LinkedList，LinkedMap等(两个JDK底层也做了N多优化)
1.3.3 栈Stack

栈, 最主要的是要实现先进后出，后进先出的逻辑结构。来保证一些场景对逻辑顺序的要求。
常用的方法有push(element)压栈，pop()出栈。

  • Java中: java.util.Stack, Jvm里面的线程栈
1.3.4 队列

队列是一种特殊的线性数据结构，队列只能允许在队头，队尾进行添加和查询等相关操作。
队列又有单项有序队列，双向队列，阻塞队列等。
基本操作方法有：add(E e)加入队列，remove(),poll()等方法。

  • Java中: 线程池，MQ，连接池等。
1.3.5 串

串：也称字符串，是由N个字符组成的优先序列。

  • 在Java里面就是指String, 而String里面是由chat[]来进行储存(KMP算法)。
  • KMP算法: 一种 字符串的查找匹配算法
    • 算法关键点: 在字符串比对的时候，主串的比较位置不需要回退(利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间)

1.4 非线性数据结构

常见的线性数据结构有：多维数组，集合，树，图，散列表(hash)。

1.4.1 多维数组

多维数组无非就是String [][],int[][]等

  • Java里面很少提供这样的工具类，而java里面tree和图底层的native方法用了多维数组来储存。
1.4.2 集合
  • 由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。
1.4.3 树
  1. 树的特点: 有且仅有一个根节点; 其他结点有且只有一个直接父节点; 可以有任意多个直接子节点
  2. 树的数据结构又分为：
    1. 自由树/普通树：对子节点没有任何约束。
    2. 二叉树：每个节点最多含有两个子节点的树称为二叉树。
      • 一般二叉树, 完全二叉树, 满二叉树
    3. 二叉搜索树/BST：binary search tree,又称二叉排序树、二叉查找树。是有序的。
      • 二叉平衡树，AVL树，红黑树
    4. B-tree：又称B树、B-树, 又叫平衡(balance)多路查找树, 每个节点存储M/2到M个关键字，所有关键字在整颗树中出现，且只出现一次，非叶子节点可以命中；
    5. B+tree：又称B+树, 在B树基础上，为叶子节点增加链表指针，所有关键字都在叶子节点中出现(有序)，叶子节点才命中；
    6. Btree：又称B树, 在B+树基础上，为非叶子节点也增加兄弟链表指针，将节点的最低利用率从1/2提高到2/3；
  3. 红黑树的5条性质：
    • 每个结点要么是红的，要么是黑的。
    • 根结点是黑的。
    • 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
    • 如果一个结点是红的，那么它的俩个儿子都是黑的。
    • 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
  4. B+树的三个特点：
    1. 关键字数和子树相同
      • 在 B+ 树中，节点的关键字代表子树的最大值，因此关键字数等于子树数。
    2. 非叶子节点仅用作索引，它的关键字和子节点有重复元素
      • 除叶子节点外的所有节点的关键字，都在它的下一级子树中同样存在，最后所有数据都存储在叶子节点中。
      • 根节点的最大关键字其实就表示整个 B+ 树的最大元素。
    3. 叶子节点用指针连在一起
      • 叶子节点包含了全部的数据，并且按顺序排列，B+ 树使用一个链表将它们排列起来，这样在查询时效率更快。
1.4.4 Hash
  • Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），变换成固定长度的输出，该输出就是散列值。一般通过Hash算法实现。（如：MD5,SHA1,加解密算法等）
  • 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
  • Java中的hashCode：
    • 默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。最大的特性是：不同的对象，不同的值有可能计算出来的hashCode可能是一样的。
  • Hash表：
    • Hash表综合了数组和链表两种数据结构。如：HashTable,HashMap。哈希表具有较快（常量级）的查询速度，及相对较快的增删速度，所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”，我们可以理解为“链表的数组”。
  • 需要注意的是，相同的内容算出来的hash一定是一样的。既：幂等性。
1.4.4.5 图
  • 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

2. 时间复杂度与空间复杂度

理解了Java数据结构，还必须要掌握一些常见的基本算法。 理解算法之前必须要先理解的几个算法的概念：

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

2.1 时间复杂度

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。

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

有时候，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同，如在冒泡排序中，输入数据有序而无序，其结果是不一样的。此时，我们计算平均值。

常见的算法的时间 复杂度之间的关系为：O(1)<O(logn)<O(n)<O(nlog n)<O(n2)<O(2n)<O(n!)<O(nn)

2.2 空间复杂度

空间复杂度：算法所需存储空间的度量，记作：S(n)=O( f(n) )，其中 n 为问题的规模。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。如果额外空间相对于输入数据量来说是个常数，则称此算法是原地工作。

算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。

3.算法的基本概念

  • 算法: 简单来说就是解决问题的步骤。
  • 算法的五个特征:有穷性，确定性，可行性，有输入，有输出
    1. 有穷性：对于任意一组合法输入值，在执行又穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。
    2. 确定性：在每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。
    3. 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。
    4. 有输入：作为算法加工对象的量值，通常体现在算法当中的一组变量。有些输入量需要在算法执行的过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。
    5. 有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法功能。
  • 算法的设计原则：正确性，可读性，健壮性，高效率与低存储量需求
    • 描述算法的速度必须要和数据项的个数联系起来。
    • 算法的存储量，包括： 程序本身所占空间； 输入数据所占空间； 辅助变量所占空间；
    • 一个算法的效率越高越好，而存储量是越低越好。

4. 常用的查找算法

4.1 线性（顺序）查找算法

  1. 使用目标元素与样本数列中第一个元素起依次进行比较
  2. 若目标元素等于样本元素，则表示查找成功
  3. 若目标元素与样本元素比较完毕也不相等，则表示查找失败

4.2 二分查找算法

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好，占用系统内存较少；其缺点是要求待查表为有序表，且插入删除困难。

  • 普通循环实现二分查找算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void main(String[] args) {
    int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
    System.out.println(binSearch(srcArray, 28));
}
/**
 * 二分查找普通循环实现
 *
 * @param srcArray 有序数组
 * @param key 查找元素
 * @return
 */
public static int binSearch(int srcArray[], int key) {
    int mid = srcArray.length / 2;
    if (key == srcArray[mid]) return mid;
    int start = 0;
    int end = srcArray.length - 1;
    while (start <= end) {
        mid = (end - start) / 2 + start;
        if (key < srcArray[mid]) {
            end = mid - 1;
        } else if (key > srcArray[mid]) {
            start = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

二分查找算法如果没有用到递归方法的话，只会影响CPU。对内存模型来说影响不大。时间复杂度log2n，2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛，平衡树里面大量采用。

  • 递归实现二分查找递归实现算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static void main(String[] args) {
    int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
    System.out.println(binSearch(srcArray, 0,15,28));
}
/**
 * 二分查找递归实现
 *
 * @param srcArray  有序数组
 * @param start 数组低地址下标
 * @param end   数组高地址下标
 * @param key  查找元素
 * @return 查找元素不存在返回-1
 */
public static int binSearch(int srcArray[], int start, int end, int key) {
    int mid = (end - start) / 2 + start;
    if (srcArray[mid] == key) {
        return mid;
    }
    if (start >= end) {
        return -1;
    } else if (key > srcArray[mid]) {
        return binSearch(srcArray, mid + 1, end, key);
    } else if (key < srcArray[mid]) {
        return binSearch(srcArray, start, mid - 1, key);
    }
    return -1;
}

递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。

4. 常用的排序算法

  • 八大排序算法
    • 一、直接插入排序（Insertion Sort）
    • 二、希尔排序（Shell Sort）
    • 三、选择排序（Selection Sort）
    • 四、堆排序（Heap Sort）
    • 五、冒泡排序（Bubble Sort）
    • 六、快速排序（Quick Sort）
    • 七、归并排序（Merging Sort）
    • 八、基数排序（Radix Sort）

4.1 冒泡排序算法

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  • 算法描述：

    1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
    2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
    3. 针对所有的元素重复以上的步骤，除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。

  • 代码实现：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public static void bubbleSort(int[] arr){
        for (int i=1; i<arr.length; i++){
          boolean flag = true;//声明标志位
          for(int j=0; j<arr.length-i; j++){
            if(arr[j] > arr[j+1]){
              int temp = arr[j+1];
              arr[j] = arr[j+1];
              arr[j++1] = temp;
              flag = false;
            }
          }
          //若此轮结束flag还是为true,则证明已经有序
          if(flag) break;
        }
    }

  • 冒泡排序算法复杂度:

    • 平均时间复杂度O(n²)，最好情况O(n)，最坏情况O(n²)，空间复杂度O(1)
    • 冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).

Tips:由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。