揭开数组的真面目

小灰灰 2021-09-18 05:50 150阅读 0赞

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

![format_png][]

## 一 数组初始化 ##

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

**第一种**：

数据类型[] 数组名称 = 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`数组，数组中已经有两个元素，则添加第三个元素如下：

![format_png 1][]

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的元素，如下：

![format_png 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`的元素。

![format_png 3][]

首先，将索引为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)。

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>线性查找</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>二分法查找</td> 
   <td>O(logN)</td> 
  </tr> 
  <tr> 
   <td>无序数组插入</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>有序数组插入</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>无序数组删除</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>有序数组删除</td> 
   <td>O(N)</td> 
  </tr> 
 </tbody> 
</table>

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

--------------------

## 关注我、不迷路 ##

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

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

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

[format_png]: /images/20210918/946d46ad9af24eb590119b5058c9265b.png
[format_png 1]: /images/20210918/3bb128f5e0e043b3b294485217060397.png
[format_png 2]: /images/20210918/aeb84715b39f4d998a038b1c7782cfb2.png
[format_png 3]: /images/20210918/abd7b1ec195e47c4b816c2e0037b1941.png