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

数据结构和算法的概述

  • 数据结构 对计算机内存中的数据的一种安排。
    • 常见数据结构 数据结构 优点 缺点 数组 插入快(根据下标) 查找慢,删除慢,大小固定 有序数组 比无序数组查找快 删除和插入慢,大小固定 栈 提供后进先出的存取方式 存取其他项很慢 队列 提供先进先出的存取方式 存取其他项很慢 链表 插入快 删除快 查找慢 二叉树 插入 查找删除都快(树平衡的情况下) 删除算法比较复杂 红黑树(平衡树) 插入 查找删除都快 算法复杂 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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

java基础之泛型

泛型 术语 "?"通配符 通配符的扩展 自定义泛型方法 "擦除"实例 类型参数的类型推断 自定义泛型类 泛型方法和泛型类的比较 泛型和反射 通过反射获...

2536
来自专栏lulianqi

ArrayList List<T> T[] Array

不保证会对 ArrayList 排序。 在执行需要对 ArrayList 排序的操作(如 BinarySearch)之前,必须对 ArrayList 进行排序。

701
来自专栏一个会写诗的程序员的博客

《Kotlin 极简教程 》第6章 泛型

通常情况的类和函数,我们只需要使用具体的类型即可:要么是基本类型,要么是自定义的类。

1023
来自专栏每日一篇技术文章

Swift3.0 - 枚举

732
来自专栏noteless

-1-3 java集合框架基础 java集合体系结构 Collection 常用java集合框架 如何选择集合 迭代器 泛型 通配符概念 Properties 集合 迭代器

                        数组可以是基本类型,也可以是引用类型

1152
来自专栏一“技”之长

Swift3.0带来的变化汇总系列二——集合类型中的变化

    与字符串类似,Swift中集合的类型在3.0版本中也做了大量API上面的修改。

701
来自专栏好好学java的技术栈

“面试不败计划”:集合知识整体总结

1303
来自专栏java学习

Java每日一练(2017/7/19)

本期题目: (单选题) 1、设int x=1,float y=2,则表达式x/y的值是:() A 0 B 1 C 2 D 以上都不是 ---- (单选题)2、若...

2858
来自专栏Java学习网

Java中实现解码字符串的方法,实用代码

需求:给定一个经过编码的字符串,要求返回它的解码后的字符串。 编码规则是:k[str],这个编码的含义是str出现了k次,k是一个正整数。 具体例子: s = ...

2515
来自专栏郭耀华‘s Blog

Java容器类List、ArrayList、Vector及map、HashTable、HashMap的区别与用法

Java容器类List、ArrayList、Vector及map、HashTable、HashMap的区别与用法 ArrayList 和Vector是采用...

3738

扫码关注云+社区