数据结构与算法——数组（基础篇）
博主也是第一次当博主，想要做一名名副其实的程序员，当然本质可能还是个商科生，看到博客的朋友可以一起交流经验，wechat：LYI_1998
数组的定义：
数组(Array)：是一种线性表结构。它用一组连续的内存空间来存储一组具有相同类型的数据，同时它也是最基础的数据结构。
！此处应有线性表概念：数据排成一条线，每个线性表上的数据最多只有前后两个方向。常见的线性表数据结构有：数组、链表、队列和栈等。
！此处应有有疑问，什么是非线性表？其中就有树、堆、图等数据结构。它们的数据之间并不是简单的前后关系，所以是非线性的。
下面正式介绍数组的使用！
一般我们都是利用数组进行增删查数据，众所周知，数组查询速度较快，插入删除数据较慢，这个是为何？看下面！
数组的查询
根据我学习的专栏《数据结构与算法之美》知识得知，对于下述代码，
int[] arr = new int[10];
系统通常会这样分配地址：
一维数组：
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)
数组的插入
若从第k位插入，则后续所有数据往后移，此举是为了保证内存的连续性。
只记得平均时间复杂度：O(n)
特殊情况提高效率：如果不是有序数组，那么可以直接把第k个位置上的数据移动到最后，然后将要插入的数据放在k位置上，这样时间复杂度就为：O(1)
数组的删除
删除int[n]数组的第k个位置上的数据，需要将k~n之间的数据往后移，这是为了保证内存的连续性。
平均时间复杂度：O(n)
特殊情况：标记统一删除法
类似于Java虚拟机中的垃圾回收算法的思想：先给要删除的元素标记为已删除元素，等到分配的内存空间不够用的时候，给标记为已删除的元素再统一删除掉，这样就可以减少数据搬移的次数。
大多数主流虚拟机采取可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有GC ROOTS，将所有GC ROOTS可达的对象标记为存活。只有当标记成功后清理工作才开始。
不足：
一是效率，标记和清理效率不高，只有少量垃圾产生才高效；
二是空间，会产生不连续的内存空间碎片。
PS：这里借鉴专栏评论区同学通俗易懂的解释：
日常生活中的垃圾，也是标记为垃圾后放进垃圾桶，然后再统一地倒垃圾！！！
数组和容器
| 数组 | 容器 |
|---|---|
| 存储基本数据类型以及引用数据类型 | 存储引用数据类型 |
| 长度固定 | 长度可变 |
| 存储元素必须为统一数据类型 | 存储可不唯一数据类型 |
PS：ArrayList(底层用数组实现)
数组增删查改代码实现
package data_structure;
public class MyArray {
// 定义数组以及初始个数
private int[] array;
private int size = 0;
public MyArray() {
// TODO Auto-generated constructor stub
array = new int[55];
}
// 插入操作，按顺序
public void insert(int value) {
int i;
// 比较大小好顺序插入
for (i = 0; i < size; i++) {
if (array[i] > value) {
break;
}
}
// 将插入位置及之后的元素后移一位，最后一位先开始移动
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 < index; i++) {
// 覆盖方法
array[i] = array[i + 1];
}
size--;
}
}
// 修改操作
public void modify(int index, int value) {
array[index] = value;
}
// 查找操作：根据值二分查找
public int binarySearch(int value) {
int lo = 0, hi = size, mid = 0;
while (true) {
mid = (lo + hi) / 2;
if (array[mid] == value) {
return mid;
} else if (array[mid] <value) {
lo = mid + 1;
} else if (array[mid] > value) {
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 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 index = arr.binarySearch(10);
System.out.println(index);
System.out.println("why?");
int data = arr.search(3);
System.out.println(data);
// 修改数据
arr.modify(2, 60);
arr.display();
// 删除数据
arr.delete(4);
arr.delete(0);
arr.display();
}
}
}
数组的动态扩容
方法一：自定义自动扩容
参考数组
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;
}
}
方法二：JDK自带扩容算法：Array.copyOf(array,newLength);
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;
}
}
参考：
1.极客时间的《数据结构与算法之美》专栏
2.数据结构与算法——数组
