HelloWorld
登录

java数据结构与算法之数组篇

Wesley13

2021-10-11

1344 1 0

数据结构和算法的概述

  • 数据结构

    对计算机内存中的数据的一种安排。

    • 常见数据结构

      数据结构

      优点

      缺点

      数组

      插入快(根据下标)

      查找慢，删除慢，大小固定

      有序数组

      比无序数组查找快

      删除和插入慢，大小固定

      栈

      提供后进先出的存取方式

      存取其他项很慢

      队列

      提供先进先出的存取方式

      存取其他项很慢

      链表

      插入快 删除快

      查找慢

      二叉树

      插入 查找删除都快(树平衡的情况下)

      删除算法比较复杂

      红黑树(平衡树)

      插入 查找删除都快

      算法复杂

      2-3-4树(平衡树)

      插入 查找删除都快

      算法复杂

      哈希表

      插入快，通过关键字存取快(key/value)

      删除慢

      堆

      插入 删除快，对最大数据项存取快

      对其他数据项存取慢

      图

      对现实世界建模

      有些算法慢且复杂

  • 算法

    对结构中的数据进行各种处理

    • 常见算法

      插入排序，简单排序，选择排序，冒泡排序等等

java数据结构与算法之数组

  • 数组介绍

    数组基本要提供创建，插入，查找，删除功能。

    • 创建的话，在创建的时候需要指定数组大小，创建完毕后，数组大小便为固定。
    • 插入的话，默认是无序的，所以数组元素的顺序是你插入的数据顺序，下标依次增加。
    • 查找的话，如果你知道下标，你可以很快的查询到，如果根据value的话，你需要遍历整个数组，如果你要查询的元素在第一个，则查找一次即可，如果在末尾则需要查找数组大小的次数。
    • 删除的话，你首先需要进行查找，定位到元素，然后进行删除，如果你删除的是第一个元素，在删除完毕之后，会对数组进行移动，把删除位置之后的元素统一往前移动。

  • java中数组的例子

    • java版的简单数组实现

      package com.arithmetic.array;

      import java.util.Arrays;

      /** * Created by bgt on 2017/10/15. * 简单的数组java实现 * 主要是java版本的基础版 */ public class SimpleArray { private int[] arr;//数组对象

      1/\*\*
2 \* 初始化数组大小和实例
3 \* @param size
4 \*/
5public SimpleArray(int size) {
6    this.arr = new int\[size\];
7}
8/\*\*设置元素\*/
9public void  setElement(int index,int val){
10    arr\[index\]=val;
11}
12/\*\*获取元素\*/
13public int  getElement(int index){
14   return arr\[index\];
15}
16
17
18@Override
19public String toString() {
20    return "SimpleArray{" +
21            "arr=" + Arrays.toString(arr) +
22            '}';
23}
24
25/\*\*
26 \* 使用示例
27 \* @param args
28 \*/
29public static void main(String\[\] args) {
30    SimpleArray array=new SimpleArray(10);
31    array.setElement(0,22);
32    array.setElement(1,26);
33    array.setElement(2,20);
34    array.setElement(3,28);
35    array.setElement(4,21);
36    System.out.println(array.getElement(4));
37}

      }

    • java版的高级数组实现

      package com.arithmetic.array;

      /** * Created by bgt on 2017/10/15. * 高级数组 * 包含插入 查找 删除 显示 */ public class SeniorArray { private int[] arr;//具体数组类型 private int totalsize;//已有数组数量

      1/\*\*
2 \* 创建数组实例，并设置大小
3 \* @param size
4 \*/
5public SeniorArray(int size) {
6    this.arr = new int\[size\];
7    this.totalsize=0;
8}
9
10/\*\*
11 \* 添加数组元素
12 \* @param val
13 \*/
14public void insert(int val){
15    arr\[totalsize++\]=val;
16}
17/\*\*
18 \* 删除数组元素
19 \* @param val
20 \*/
21public void del(int val){
22   int delindex=findIndex(val);
23    if (delindex<totalsize) {
24        for (int i = delindex; i < totalsize; i++) {
25            arr\[i\]=arr\[i+1\];
26        }
27    totalsize--;
28    }
29}
30
31/\*\*
32 \* 查找数组元素
33 \* @param val
34 \*/
35public int findIndex(int val){
36    int searchIndex=totalsize;//默认是元素数量
37    for (int i = 0; i < arr.length; i++) {
38        if (arr\[i\]==val) {
39           searchIndex=i;
40           break;
41        }
42    }
43    System.out.println("val:"+val+",index:"+searchIndex);
44    return searchIndex;
45}
46/\*\*
47 \* 查找数组元素
48 \* @param index
49 \*/
50public int findByIndex(int index){
51   return  arr\[index++\];
52}
53
54/\*\*
55 \* 遍历 数组元素
56 \*/
57public void display(){
58    for (int i=0;i<totalsize;i++) {
59        System.out.print(arr\[i\]+",");
60    }
61    System.out.println("----------------------------------");
62}
63
64public static void main(String\[\] args) {
65    SeniorArray seniorArray=new SeniorArray(10);
66    seniorArray.insert(2);
67    seniorArray.insert(5);
68    seniorArray.insert(3);
69    seniorArray.insert(1);
70    seniorArray.insert(42);
71    seniorArray.insert(6);
72    System.out.println(seniorArray.totalsize);
73    seniorArray.display();
74    seniorArray.del(1);
75    seniorArray.display();
76}

      }

有序数组以及线性查找和二分查找比较

有序数组

  • 优点

查找速度比无序数组快多了

  • 缺点

插入时要按排序方式把后边的数据进行移动。

  • 与无序数组共同的缺点

删除数据时必须把后边的数据向前移动来填充删除项的空缺。

有序数组Java实现

ArrayInterface.java

package com.arithmetic.array;

import java.util.Arrays;

/** * Created by baiguantao on 2017/10/17. */ public interface ArrayInterface {

1void insert(int val);//插入
2int find(int val);//查找
3int size();//已有元素数量
4void del(int val);//删除
5
6/\*\*
7 \* 默认显示array方法
8 \* @param arr
9 \*/
10default void displayAll(int\[\] arr){
11    int total=size();
12    Arrays.stream(arr).limit(total).forEach(a->{
13        System.out.println(a);
14    });
15}

}

OrderArray.java

package com.arithmetic.array;

/** * Created by baiguantao on 2017/10/17. * 有序数组 */ public class OrderArray implements ArrayInterface{ public int[] arr; public int size;//已有元素数量 public OrderArray(int maxsize) { this.arr = new int[maxsize]; size=0; }

1/\*\*
2 \* 这里是有序数组
3 \* 线性查找示例
4 \* 找到当前元素适合插入的问题
5 \* 随后对元素进行移动操作
6 \* @param val
7 \*/
8@Override
9public void insert(int val) {
10    //查找适合的位置
11    int realpostion=0;
12    for (realpostion=0;realpostion<size;realpostion++) {
13        if(arr\[realpostion\]>val)break;//如果当前元素比val大，则终止循环（这里默认是有序递增形式数组）
14    }
15    //进行元素置换  k是元素数量 比下标错开1位 下标从0 开始 所以k 其实对应下标+1 这样子
16    for (int k=size;k>realpostion;k--) {
17        arr\[k\]=arr\[k-1\];
18    }
19    arr\[realpostion\]=val;
20    size++;
21}
22
23/\*\*
24 \* 二分查找
25 \* @param val
26 \* @return
27 \*/
28@Override
29public int find(int val) {
30    int first=0;//二分当前范围的起始位置
31    int last=size-1;//二分当前范围的结束位置
32    int mid;//二分当前范围的中间值
33
34    while (true){
35        mid=(first+last)/2;
36        if (arr\[mid\]==val) {//如果刚好与查找的一致，则返回下标
37            return mid;
38        }else if (first>last){//未查到则返回数组大小
39            return size;
40        }else{
41            //当前值大于中间下标
42            if (arr\[mid\]<val) {
43                first=mid+1;
44            }else{
45                last=mid-1;
46            }
47        }
48    }
49}
50
51@Override
52public int size() {
53    return size;
54}
55
56/\*\*
57 \* 数组删除 并移动数组元素
58 \* @param val
59 \*/
60@Override
61public void del(int val) {
62    int valindex=find(val);
63    if (valindex==size) {//未查到下标
64        System.out.println("未查到");
65    }else{
66        for (int k=valindex;k<size;k++) {//移动后边数组
67            arr\[k\]=arr\[k+1\];
68        }
69        size--;
70        System.out.println("查到了，进行数组移动...");
71    }
72}
73
74static  boolean b;
75public static void main(String\[\] args) {
76    OrderArray orderArray=new OrderArray(10);
77    orderArray.insert(3);
78    orderArray.insert(6);
79    orderArray.insert(5);
80    orderArray.insert(4);
81    orderArray.insert(1);
82    orderArray.displayAll(orderArray.arr);
83    orderArray.del(4);
84    orderArray.displayAll(orderArray.arr);
85  /\*  int x=0;
86    if (b) {
87        x=1;
88    }else  if (b=false) {
89        x=2;
90    }else  if (b) {
91        x=3;
92    }else  {
93        x=4;
94    }
95    System.out.println("x:"+x);\*/
96}

}

线性查找

其实我们默认使用的就是线性查找。虽然也可以实现查找，但是时间复杂度是N,相对来说比较耗时。 我们在插入的时候采用线性方式来实现。如下所示：

/** * 这里是有序数组 * 线性查找示例 * 找到当前元素适合插入的问题 * 随后对元素进行移动操作 * @param val */ @Override public void insert(int val) { //查找适合的位置 int realpostion=0; for (realpostion=0;realpostion<size;realpostion++) { if(arr[realpostion]>val)break;//如果当前元素比val大，则终止循环（这里默认是有序递增形式数组） } //进行元素置换 k是元素数量 比下标错开1位 下标从0 开始 所以k 其实对应下标+1 这样子 for (int k=size;k>realpostion;k--) { arr[k]=arr[k-1]; } arr[realpostion]=val; size++; }

二分查找

使用二分查找的前提是数据是有序的 我们在查找的方法中用二分查找的方式来实现

/** * 二分查找 * @param val * @return */ @Override public int find(int val) { int first=0;//二分当前范围的起始位置 int last=size-1;//二分当前范围的结束位置 int mid;//二分当前范围的中间值

1    while (true){
2        mid=(first+last)/2;
3        if (arr\[mid\]==val) {//如果刚好与查找的一致，则返回下标
4            return mid;
5        }else if (first>last){//未查到则返回数组大小
6            return size;
7        }else{
8            //当前值大于中间下标
9            if (arr\[mid\]<val) {
10                first=mid+1;
11            }else{
12                last=mid-1;
13            }
14        }
15    }
16}

  • 二分查找比较次数

    数据量

    比较次数

    10

    1

    1000

    7

    10000

    10

    10000

    14

    100000

    17

    1000000

    20

    10000000

    24

    100000000

    27

    1000000000

    30

后记

后续会继续堆栈链表哈希树等的示例。不对之处望大家指正。

ricky 20171017

交流群：244930845

点赞
收藏

评论区

加载中...

相关推荐

MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1

文章目录问题用navicat导入数据时，报错：原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等，这样可以更容易地在不同的环境中使用MySQL。全局s

Oracle 分组与拼接字符串同时使用

SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(

MySQL部分从库上面因为大量的临时表tmp_table造成慢查询

背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_

皕杰报表之UUID

​在我们用皕杰报表工具设计填报报表时，如何在新增行里自动增加id呢？能新增整数排序id吗？目前可以在新增行里自动增加id，但只能用uuid函数增加UUID编码，不能新增整数排序id。uuid函数说明：获取一个UUID，可以在填报表中用来创建数据ID语法：uuid()或uuid(sep)参数说明：sep布尔值，生成的uuid中是否包含分隔符''，缺省为

手写Java HashMap源码

HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22

2020年前端实用代码段，为你的工作保驾护航

有空的时候，自己总结了几个代码段，在开发中也经常使用，谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )