【数据结构与算法】之数组---第二篇
先来看下数组的定义：
数组(Array)：是一种线性表结构。它用一组连续的内存空间来存储一组具有相同类型的数据，同时她也是最基础的数据结构。
提到数组就不得不说线性表： 数据排成一条线，每个线性表上的数据最多只有前后两个方向。常见的线性表数据结构有：数组、链表、队列和栈等。（这里引用下极客时间关于《数据结构与算法之美》的专栏中的图片，这个专栏很不错，推荐给大家）
与线性表对立的就是非线性表，比如树、堆、图等数据结构。它们的数据之间并不是简单的前后关系，所以是非线性的。至于它们的区别，后面的博客中会逐一分析到。
前面根据线性和非线性对集中常见的数据结构做了划分，那么下面正式开始本篇博文的主题讲解：数组的使用
数组给我们最大的印象就是：查询数据快，但是插入和删除数据较慢，那么解释这个原因就必须回归到底层的数据结构了。我这里继续引用极客时间中的案例：
1 数组的查询操作：
比如：我们现在要创建一个大小为10的int型数组：下面这段代码会发生什么？
int[] arr = new int[10]; 计算机会给arr数组分配一块连续的内存空间，会给每个内存单元分配一个地址，计算机就是通过地址来访问内存中的数据。其中内存块的首地址为base_address = 1000。当我们要随机访问数组中的某个元素的时候，它会通过寻址公式:
一维数组：
a[i]_address = base_address + i * data_type_size
m*n数组：a[i][j](i < m, j < n)的寻址公式为：
a[i][j]_address = base_address + (i * n + j) * data_type_size
说明：data_type_size表示数组中每个元素的大小，即几个字节
计算出该元素的内存地址，所以可以看出根据下标随机访问数组中的某个元素的时间复杂度为O(1)。
2 数组的插入操作：
若往int[n]数组的第k个位置插入数据，需要将k~n之间的数据往后移，这是为了保证内存的连续性。
最好情况时间复杂度：O(1) 数组末尾位置插入
最坏时间复杂度：O(n) 数组的开头位置
平均时间复杂度：O(n)
提高效率的一种方法：如果不是有序数组，那么可以直接把第k个位置上的数据移动到最后，然后将要插入的数据放在k位置上，这样时间复杂度就为：O(1)。
3 数组的删除操作：
若要删除int[n]数组的第k个位置上的数据，需要将k~n之间的数据往后移，这是为了保证内存的连续性。
最好情况时间复杂度：O(1) 数组末尾位置插入
最坏时间复杂度：O(n) 数组的开头位置
平均时间复杂度：O(n)
提高效率的一种方法：类似于Java虚拟机中的垃圾回收算法的思想：先给要删除的元素标记为已删除元素，等到分配的内存空间不够用的时候，给标记为已删除的元素再统一删除掉，这样就可以减少数据搬移的次数。
4 数组与容器：
提到数组，就不得不说容器类，想必很多人也是傻傻分不清该如何使用.......下面主要介绍下Java中数组与容器的区别以及该如何选择使用？
区别：
1、数组既可以存储基本数据类型，也可以存储引用数据类型，而容器只能存储引用数据类型；
2、数组的长度是固定的，容器的长度是可变的；
3、数组存储的元素必须是同一种数据类型，而容器存储的引用对象可以是多种类型。
选择：
如果要存储的数据的类型为基本数据类型，或者数据大小已知，并且只涉及简单的数据操作，这时候可以直接选择数组。其他情况直接使用Jdk给我们提供的集合类就行，比如常用的ArrayList(底层用数组实现)。
5 实现自定义数组的增删改查
public class MyArray {
private int[] array; // 定义一个数组
private int size = 0; // 这个数组中元素的个数，初始值默认为0
public MyArray(){
array = new int[50]; // 看一下怎么自动扩容
}
// 插入数据,按顺序插入
public void insert(int value){
int i;
for(i = 0; i < size; i++){
if(array[i] > value){
break;
}
}
// 将i及i以后的位置上的元素往后移动一位,最后一位先开始移
for(int j = size; j > i; j--){
array[j] = array[j-1]; // 往后移动一位
}
// 将要添加的元素添加到位置i处
array[i] = value;
size++;
}
// 删除数组中的元素
public void delete(int index){
if(index < 0 || index >= size){
throw new ArrayIndexOutOfBoundsException();
}else{
for(int i = index; i < size; i++){
array[i] = array[i + 1]; // 通过覆盖的方法，index以后的元素都往后移动一个位置
}
}
size--;
}
// 修改数组中的元素
public void modify(int index, int value){
array[index] = value; // 直接将value覆盖掉以前的值就可以了
}
// 查询操作（根据值进行二分查找）
public int binarySearch(int value){
int lo = 0;
int hi = size;
int mid = 0;
while(true){
mid = (lo + hi) / 2;
if(array[mid] == value){
return mid;
}
else if(array[mid] < value){ // 说明value在array[mid, hi]中
lo = mid + 1;
}
else if(array[mid] > value){ // 说明value在array[lo,mid]中
hi = mid - 1;
}
}
}
// 根据下标查询
public int search(int index){
return array[index];
}
// 显示数组
public void display(){
System.out.print("[");
for(int i = 0; i < size; i++){
System.out.print(array[i] + ",");
}
System.out.print("]");
}
}测试代码：
public class TestMyArray {
public static void main(String[] args) {
MyArray arr = new MyArray();
// 插入数据
arr.insert(10);
arr.insert(20);
arr.insert(30);
arr.insert(40);
arr.insert(50);
// 显示数据
arr.display();
// 查找数据
int index1 = arr.binarySearch(10);
System.out.println(index1);
int data = arr.search(3);
System.out.println(data);
// 修改数据
arr.modify(2, 60);
arr.display();
// 删除数据
arr.delete(4);
arr.delete(0);
arr.display();
}
}
6 数组的动态扩容
方式一：自定义自动扩容数组
我们都知道数组一旦创建其大小不可改变，一旦数组中的元素个数已经达到了数组的大小，那么就不能再往数组中插入数据了，否则就会造成数组越界，所以非常的不方便。那么我们也可以自定义自动扩容数组，当数组没有内存空间的时候，还要往里面插入数据，就会自动扩展其内存空间。具体代码如下：
public class DynamicArray {
private static int[] arr;
private static int size = 0;
public DynamicArray(){
arr = new int[2]; // 初始内存空间大小为10
}
public static int[] insert(int index, int num){
if(index < 0){
throw new ArrayIndexOutOfBoundsException(); // 数组越界
}
// 先判断数组是否已经存满
int[] brr = null;
if(arr.length == size){
brr = expandArray(arr); // 扩容
for(int i = arr.length - 1; i > index; i--){
brr[i] = arr[i-1]; // 迁移数组
}
brr[index] = num; // 插入数组
arr = brr; // 将变量arr指向扩容后的数组brr
}else{
for(int i = arr.length - 1; i > index; i--){
arr[i] = arr[i-1];
}
arr[index] = num;
}
size ++;
return arr;
}
// 扩容
public static int[] expandArray(int[] arr){
int[] brr = new int[arr.length * 2];
arr = brr;
return arr;
}
}测试代码：
public class TestDynamicArray {
public static void main(String[] args) {
DynamicArray drr = new DynamicArray();
drr.insert(0, 10);
drr.insert(0, 10);
drr.insert(0, 10);
drr.insert(0, 10);
drr.insert(0, 10);
drr.insert(0, 10);
int[] arr = drr.insert(1, 20);
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]);
}
}
}方式二：使用JDK中自带的数组扩容算法：Arrays.copyOf(array, newLength);
与方式一相比，只是扩容方法替换为了Java自带的函数库，其他不变，测试代码与方法一相同。
public class DynamicArray1 {
private static int[] arr;
private static int size = 0;
public DynamicArray1(){
arr = new int[2]; // 初始内存空间大小为10
}
public static int[] insert(int index, int num){
if(index < 0){
throw new ArrayIndexOutOfBoundsException(); // 数组越界
}
// 先判断数组是否已经存满
int[] brr = null;
if(arr.length == size){
brr = expandArray(arr); // 扩容
for(int i = arr.length - 1; i > index; i--){
brr[i] = arr[i-1]; // 迁移数组
}
brr[index] = num; // 插入数组
arr = brr; // 将变量arr指向扩容后的数组brr
}else{
for(int i = arr.length - 1; i > index; i--){
arr[i] = arr[i-1];
}
arr[index] = num;
}
size ++;
return arr;
}
public static int[] expandArray(int[] arr){
arr = Arrays.copyOf(arr, arr.length * 2); // 每次扩容一倍
return arr;
}
}引用及推荐：
需要在此说明的是：本篇博客的大部分图片以及部分案例来自极客时间的《数据结构与算法之美》专栏。真的是很好的专栏，我也是购买了这个专栏，然后才有想法结合自己看的书、大牛的博文以及专栏汇总为自己方便理解的形式，以博客的形式记录下来，方便以后复习。
学习不会是单打独斗，如果你也是做Java开发，可以加我微信，一起分享经验学习!
本人微信号：pengcheng941206