揭开数组的真面目

Java旅途

关注

发布于: 2020 年 08 月 29 日

数组做为一种基础的数据存储结构，应用十分广泛。数组是用连续的内存空间来存储固定长度的、*相同数据类型*的一种数据结构。数据结构是跟语言无关的，这里，使用 java 来进行数组的相关操作。数组的索引是从 0 开始的。

一数组初始化

创建数据有两种方式，一种是先声明一个固定长度的数据，然后再给数组赋值，另一种是直接赋值。

第一种：

数据类型[] 数组名称 = new 数据类型[长度];

复制代码

这里的[]标识这声明了一个数组，这个[]除了可以放在数据类型后面，也可以放在数组名词后面，效果一样。假如我申明一个长度为2的long类型的数组，并赋值：

long[] arr = new long[2];arr[0] = 1;arr[1] = 2;

复制代码

第二种：

数据类型[] 数组名称 = {元素1,元素2, ...};

复制代码

这样在数组初始化的时候直接给数组赋值，数组的长度由元素的个数决定。

二自定义类封装数组实现数据操作

public class MyArray {	    // 自定义数组    private long[] arr;    // 有效数据长度    private int element;
    public MyArray(){        arr = new long[9];    }
    public MyArray(int maxsize){        arr = new long[maxsize];    }    /**     * 显示数组元素     */    public void display(){        System.out.print("[");        for (int i = 0; i < element; i++) {            System.out.print(arr[i]+" ");        }        System.out.print("]");    }}

复制代码

2.1 添加元素

数组是用连续的内存空间来存储数据的，则每次添加的时候会往当前数组的最后一个元素上添加元素，一次就可以加上元素，所以它的复杂度为 O(1)，假如定义一个长度为9数组，数组中已经有两个元素，则添加第三个元素如下：

public void add(long value){    arr[element] = value;    element++;}

复制代码

2.2 根据值查询元素位置

这种查找方式也叫做线性查找，就是根据传入的值循环去遍历元素，来获取对应的位置，理论上平均查询一个元素需要花费 N/2 次，所以它的复杂度为 O(N)。

public int find(long value){    int i;    for (i = 0; i < element; i++) {        if(value == arr[i]){            break;        }    }    if(i == element){        return -1;    }else {        return i;    }}

复制代码

2.3 根据索引查询元素

根据索引来查找元素，也就是获取对应位置的元素，其复杂度为 O(1)。

public long get(int index){    if(index >= element || index < 0){        throw new ArrayIndexOutOfBoundsException();    }else {        return arr[index];    }}

复制代码

2.4 根据索引删除元素

删除对应索引的元素后，我们需要将所有改索引后面的元素，向前移动一位。假如我要删除索引为 2 的元素，如下：

理论上平均删除一个元素，我们需要移动 N/2 次，所以它复杂度也为 O(N)。

public void delete(int index){    if(index >= element || index < 0){        throw new ArrayIndexOutOfBoundsException();    }else {        for (int i = index; i < element; i++) {            arr[index] = arr[index+1];        }        element --;    }}

复制代码

2.5 修改元素

修改某个位置的元素，直接根据索引就一次就可以修改对应的元素，所以它的复杂度为 O(1)。

public void change(int index,long newValue){    if(index >= element || index < 0){        throw new ArrayIndexOutOfBoundsException();    }else {        arr[index] = newValue;    }}

复制代码

三有序数组

有序数组是数组的一种特殊类型，有序数组中的元素按照某种顺序进行排列。

3.1 添加元素

在添加元素的时候，将元素按顺序添加到某个位置。如下，在一个数组中添加一个33的元素。

首先，将索引为 3 的元素移动到索引为 4 的位置，然后将索引为 2 的元素移动到索引为 3 的位置，最后将 33 添加到索引为 2 的位置。理论上插入一个元素需要移动元素的个数为 N/2 个，所以它的复杂度为 O(N)。

public void add(long value){    int i;    for (i = 0; i < element; i++) {        if(arr[i]>value){            break;        }    }
    for (int j = element; j > i; j--){        arr[j] = arr[j-1];    }    arr[i] = value;    element++;}

复制代码

3.2 二分法根据元素查询索引

在无序数组中，使用线性法进行查找相关元素，线性法即按索引按个查找。有序数组可以使用二分法来查找元素，二分发是指将一个数组从中间分成两个，判断元素位于哪个数组中，然后重复这样的操作。

假如有8个元素的一个数组，数组内容为有序的 0-7 的序列，要查找 5 这个元素，第一次分成 0-3 和 4-7 两个数组，然后再将 4-7 分成 4-5 和 6-7 连个数组，最后再将 4-5 分成 4 和 5 就查询出来具体的元素了，这样分割 3 次就可以查询出长度为 8 的数组中具体的元素，其复杂度即为 O(logN)（logN 在计算机中底数一般指的是 2，意思为 2 的几次方等于 n）。

public int search(long value){    // 中间值    int middle = 0;    // 最小值    int low = 0;    // 最大值    int pow = element;    while (true){        middle = (low + pow) / 2;        if(arr[middle] == value){            return middle;        }else if (low > pow){            return -1;        }else{            if(arr[middle] > value){                pow = middle - 1;            }else{                low = middle + 1;            }        }    }}

复制代码

四总结

复杂度越低意味着算法更加优秀，所以 O(1) > O(logN) > O(N) > O(N^2)。

无序数组插入快，查找和删除慢
有序数组查找快，插入和删除慢

点关注、不迷路

如果觉得文章不错，欢迎关注、*点赞*、收藏，你们的支持是我创作的动力，感谢大家。

如果文章写的有问题，请不要吝啬，欢迎留言指出，我会及时核查修改。

如果你还想更加深入的了解我，可以微信搜索「Java 旅途」进行关注。回复「1024」即可获得学习视频及精美电子书。每天 7:30 准时推送技术文章，让你的上班路不在孤独，而且每月还有送书活动，助你提升硬实力！

发布于: 2020 年 08 月 29 日阅读数: 335

原文链接:【http://xie.infoq.cn/article/fd46b2911b53148043a22601b】。

Java旅途

关注

还未添加个人签名 2020.06.17 加入

公众号：Java旅途

发布

暂无评论

创作场景

揭开数组的真面目

一 数组初始化

二 自定义类封装数组实现数据操作

2.1 添加元素

2.2 根据值查询元素位置

2.3 根据索引查询元素

2.4 根据索引删除元素

2.5 修改元素

三 有序数组

3.1 添加元素

3.2 二分法根据元素查询索引

四 总结

点关注、不迷路

Java旅途

评论

一数组初始化

二自定义类封装数组实现数据操作

三有序数组

四总结