乐趣区

关于数据结构:揭开数组的真面目

jiezi

数组做为一种根底的数据存储构造，利用非常宽泛。数组是用 间断 的内存空间来存储 固定长度 的、雷同数据类型 的一种数据结构。数据结构是跟语言无关的，这里，应用 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)。

算法 复杂度
线性查找 O(N)
二分法查找 O(logN)
无序数组插入 O(1)
有序数组插入 O(N)
无序数组删除 O(N)
有序数组删除 O(N)
  1. 无序数组插入快，查找和删除慢
  2. 有序数组查找快，插入和删除慢

关注我、不迷路

如果感觉文章不错，欢送 关注 、 点赞 、 珍藏，你们的反对是我创作的能源，感激大家。

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

如果你还想更加深刻的理解我，能够微信搜寻「Java 旅途」进行关注。回复「1024」即可取得学习视频及精美电子书。每天 7:30 准时推送技术文章，让你的下班路不在孤单，而且每月还有送书流动，助你晋升硬实力！

退出移动版