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

Wesley13
• 阅读 798

数据结构和算法的概述

  • 数据结构

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

    • 常见数据结构

      数据结构

      优点

      缺点

      数组

      插入快(根据下标)

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

      有序数组

      比无序数组查找快

      删除和插入慢,大小固定

      提供后进先出的存取方式

      存取其他项很慢

      队列

      提供先进先出的存取方式

      存取其他项很慢

      链表

      插入快 删除快

      查找慢

      二叉树

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

      删除算法比较复杂

      红黑树(平衡树)

      插入 查找删除都快

      算法复杂

      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;//数组对象 /** * 初始化数组大小和实例 * @param size */ public SimpleArray(int size) { this.arr = new int[size]; } /**设置元素*/ public void setElement(int index,int val){ arr[index]=val; } /**获取元素*/ public int getElement(int index){ return arr[index]; } @Override public String toString() { return "SimpleArray{" + "arr=" + Arrays.toString(arr) + '}'; } /** * 使用示例 * @param args */ public static void main(String[] args) { SimpleArray array=new SimpleArray(10); array.setElement(0,22); array.setElement(1,26); array.setElement(2,20); array.setElement(3,28); array.setElement(4,21); System.out.println(array.getElement(4)); } }

    • java版的高级数组实现

      package com.arithmetic.array;

      /** * Created by bgt on 2017/10/15. * 高级数组 * 包含插入 查找 删除 显示 */ public class SeniorArray { private int[] arr;//具体数组类型 private int totalsize;//已有数组数量 /** * 创建数组实例,并设置大小 * @param size */ public SeniorArray(int size) { this.arr = new int[size]; this.totalsize=0; } /** * 添加数组元素 * @param val */ public void insert(int val){ arr[totalsize++]=val; } /** * 删除数组元素 * @param val */ public void del(int val){ int delindex=findIndex(val); if (delindex<totalsize) { for (int i = delindex; i < totalsize; i++) { arr[i]=arr[i+1]; } totalsize--; } } /** * 查找数组元素 * @param val */ public int findIndex(int val){ int searchIndex=totalsize;//默认是元素数量 for (int i = 0; i < arr.length; i++) { if (arr[i]==val) { searchIndex=i; break; } } System.out.println("val:"+val+",index:"+searchIndex); return searchIndex; } /** * 查找数组元素 * @param index */ public int findByIndex(int index){ return arr[index++]; } /** * 遍历 数组元素 */ public void display(){ for (int i=0;i<totalsize;i++) { System.out.print(arr[i]+","); } System.out.println("----------------------------------"); } public static void main(String[] args) { SeniorArray seniorArray=new SeniorArray(10); seniorArray.insert(2); seniorArray.insert(5); seniorArray.insert(3); seniorArray.insert(1); seniorArray.insert(42); seniorArray.insert(6); System.out.println(seniorArray.totalsize); seniorArray.display(); seniorArray.del(1); seniorArray.display(); } }

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

有序数组

  • 优点

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

  • 缺点

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

  • 与无序数组共同的缺点

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

有序数组Java实现

ArrayInterface.java

package com.arithmetic.array;

import java.util.Arrays;

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

void insert(int val);//插入
int find(int val);//查找
int size();//已有元素数量
void del(int val);//删除

/\*\*
 \* 默认显示array方法
 \* @param arr
 \*/
default void displayAll(int\[\] arr){
    int total=size();
    Arrays.stream(arr).limit(total).forEach(a->{
        System.out.println(a);
    });
}

}

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; }

/\*\*
 \* 这里是有序数组
 \* 线性查找示例
 \* 找到当前元素适合插入的问题
 \* 随后对元素进行移动操作
 \* @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;//二分当前范围的中间值

    while (true){
        mid=(first+last)/2;
        if (arr\[mid\]==val) {//如果刚好与查找的一致,则返回下标
            return mid;
        }else if (first>last){//未查到则返回数组大小
            return size;
        }else{
            //当前值大于中间下标
            if (arr\[mid\]<val) {
                first=mid+1;
            }else{
                last=mid-1;
            }
        }
    }
}

@Override
public int size() {
    return size;
}

/\*\*
 \* 数组删除 并移动数组元素
 \* @param val
 \*/
@Override
public void del(int val) {
    int valindex=find(val);
    if (valindex==size) {//未查到下标
        System.out.println("未查到");
    }else{
        for (int k=valindex;k<size;k++) {//移动后边数组
            arr\[k\]=arr\[k+1\];
        }
        size--;
        System.out.println("查到了,进行数组移动...");
    }
}

static  boolean b;
public static void main(String\[\] args) {
    OrderArray orderArray=new OrderArray(10);
    orderArray.insert(3);
    orderArray.insert(6);
    orderArray.insert(5);
    orderArray.insert(4);
    orderArray.insert(1);
    orderArray.displayAll(orderArray.arr);
    orderArray.del(4);
    orderArray.displayAll(orderArray.arr);
  /\*  int x=0;
    if (b) {
        x=1;
    }else  if (b=false) {
        x=2;
    }else  if (b) {
        x=3;
    }else  {
        x=4;
    }
    System.out.println("x:"+x);\*/
}

}

线性查找

其实我们默认使用的就是线性查找。虽然也可以实现查找,但是时间复杂度是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;//二分当前范围的中间值

    while (true){
        mid=(first+last)/2;
        if (arr\[mid\]==val) {//如果刚好与查找的一致,则返回下标
            return mid;
        }else if (first>last){//未查到则返回数组大小
            return size;
        }else{
            //当前值大于中间下标
            if (arr\[mid\]<val) {
                first=mid+1;
            }else{
                last=mid-1;
            }
        }
    }
}
  • 二分查找比较次数

    数据量

    比较次数

    10

    1

    1000

    7

    10000

    10

    10000

    14

    100000

    17

    1000000

    20

    10000000

    24

    100000000

    27

    1000000000

    30

后记

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

ricky 20171017

交流群:244930845

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
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
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这