数据结构与算法的重温之旅（三）——数组

摘要：整个程序在存入是数据大于数组长度的时候才会发生数组的删除操作。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。

本系列所有文章的代码都是用JavaScript实现，之所以用JavaScript实现是因为它可以直接在浏览器宿主中运行代码，即在浏览器中按f12打开控制台，选择console按钮，在下面空白的文本框把本例的代码黏贴上去回车即可运行。方便各位同学学习和调试。

数组这个概念相信各位同学在日常写代码的时候肯定会经常用到，我们通常用数组作为容器来存储数据。基本上每一种编程语言都有这种数据结构，它是一个基础的数据结构，下面将仔细的讲解数组的原理及应用。

什么是数组呢？按照专业的名词解释，数组是一种线性表数据结构，它用连续的内存空间来存储一组具有相同类型的数据。从定义里我们可以看到几个关键词，分别是线性表(Linear List)和连续的内存空间和相同类型的数据。

线性表的意思其实就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等都是线性表结构。而与线性表对立的则是非线性表 ，比如二叉树、图、堆等。之所以叫非线性，是因为非线性表中的数据并不是简单的前后关系。

当我们声明一个数组的时候，计算机就会为数组分配一个连续的内存空间。假如我们声明的数组长度是10，在数组中存储的元素都说int类型的数据，如果内存的首地址为1000，则计算机为数组分配了1000~1039的连续内存空间。数组和链表不同的一点就是数组存储的都是连续的内存空间，而链表存储的都说不连续的内存空间，所以如果一个计算机的内存只有1G的情况下，我们声明了一个占用1G内存的数组很有可能会导致内存溢出，因为有可能内存里有不连续的空间，而声明1G内存的链表则不会出现这种情况。

结合上面所说的两点，数组由于是线性的并且是连续的内存空间，随机访问的时候时间复杂度非常的快，为O(1)。数组的随机访问并不需要遍历本身，只需要知道下标就可以得出值。但是有利也有弊，与快速的查询相反的就是在插入和删除的时候所要耗费更多的复杂度。在这里需要提一点的是，数组是随机查找的时候时间复杂度为O(1)，不能笼统的认为数组在执行查找操作的时候时间复杂度为O(1)，如果你用二分查找来对数组进行查找操作，耗费的时间复杂度为O(logn)。

上面提到数组由于连续的内存空间导致了在执行插入和删除操作的时候占用大量的性能。首先我们来说一下插入操作在数组的执行过程。

假设我们声明了一个数组长度为n，如果我们要插入的数组在数组第m个位置的时候，为了能够让数据成功的插入下标m当中，我们要把m到n这一部分的数据往后移一位，然后把数据放入下标m当中。那如果数据是要插入到数组最后面的话，那时间复杂度也只是O(1)，如果是在开头插入的话时间复杂度则为O(n)，因为每个位置的概率都是一样的，所以我们可以得到平均时间复杂度为：。

如果一个数组是有序的，我们为了保持数组的有序性，的确只能用上述的方法来解。但是如果数组是无序的，为了避免大规模的数据移动，我们可以把当前下标m的数据放到最后面，把我们的值放入到下标m当中。利用这个方法我们可以将时间复杂度降到O(1)，性能将极大的提升。

同理在删除中，如果我们要删除下标为m的元素，为了内存的连续性，也需要把m到n后面的数据往前移，不然就不连续。删除的最好时间复杂度是O(1)，即删除的是结尾的数据的时候。最坏时间复杂度则为O(n)，即在开头的数据被删除。它的平均时间复杂度的公式也和上面插入的公式一样，结果为O(n)。

那么如果我们对数组进行频繁的删除操作，程序的性能将会极大的降低，有时候办法可以解决呢？这个时候我们可以借助JVM标记清除垃圾回收算法来实现。当执行删除操作的时候我们并不是真的把数组里的元素给删除掉，而是给该元素标记一个删除状态，等到后面数组没有更多的空间存储数组的时候再一次性的执行删除操作，极大地减少数据的迁移。下面用JavaScript代码来简单的实现一下：

var arr = new Array(10)
var count = 0
function insertArr(obj) {
    if (typeof arr[9] === "object") {
        var tempArr = []
        for (var a = 0; a < arr.length; a++) {
            if (!arr[a].removeSign) {
                arr[a].index = tempArr.length
                arr[a].removeSign = false
                tempArr.push(arr[a])
            }
        }
        arr = tempArr
        count = tempArr.length
        if (arr.length === 10) {
            console.error("数组越界")
            return
        }
    }
    arr[count] = {
        value: obj.value,
        removeSign: false,
        index: count
    }
    count++
}
function removeArr(index){
    if (arr.length === 0) {
        console.error("数组长度为0，不能删除元素")
        return
    }
    else if (index > arr.length) {
        console.error("数组越界")
        return
    }
    // 如果当前的已标记为true则查看下一个元素是否为true，如果不是则标记为true，是的话则继续递归
    if (arr[index].removeSign) {
        return removeArr(++index)
    }
    arr[index].removeSign = true
}