讯享网

 <p><blockquote id="33S6VFPL">数组，是日常开发中用到的最多的数据结构之一，说到这里，可能有人就不赞同，“怎么我学的数组不是数据结构呢？”，看完这篇文章，我相信你能够自己判断！<br/>之前，自己一度认为数组太简单了，不就是通过下标拿元素，遍历数组，查找排序等操作。直到看了大佬对数组的介绍，才发觉自己真是坐井观天，对数组的理解太浅显了。<br/></blockquote></p><p id="33S6VFMR">数组专业一点来说是属于“<strong>线性表</strong>”的一种，它用一组连续的内存空间来存储具有相同类型的数据。</p><p id="33S6VFMS">常见的线性表结构有链表、数组、栈、队列，顾名思义<strong>线性表</strong>就是数据排列在一条线上，每个线性表上的数据最多只有<strong>前后</strong>两个方向。</p><p id="33S6VFMT"><strong>非线性表</strong>结构则比线性表更复杂，非线性表上的数据并不是简单的前后关系，常见的非线性表数据结构有图、树、堆等。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1019%2F9e15c67cj00sllqd60007d000k0005bp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1019%2F4bb8da04j00sllqdd000gd000k000bpp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="33S6VFN4">通过上面的图，我们能明显看到线性表和非线性表的不同之处。线性表只有前后关系，非线性表则存在多种关系。</p><p id="33S6VFN5">继续说数组，上面说到来数组是线性表的一种，并且数组是连续的内存空间，相同的数据类型，所以数组有通过下标“<strong>随机访问</strong>”的特性；</p><p id="33S6VFN6">但是这也带来了一些弊端，就是数组是连续的，导致删除和插入的时候为了保证连续性需要进行大量的数据迁移。</p><p id="33S6VFN7">数据的访问，那到底数组是怎么通过下标随机访问元素的呢？</p><p id="33S6VFN8">拿一个长度为10的int类型数组 int[] a = new int[10]; 计算机会给数组分配连续的内存空间 1000~1039，其中内存首地址为base_address = 1000;</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1019%2F770ccabbj00sllqdk000ad000k0008hp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="33S6VFNC">我们知道计算机会给每个内存单元分配一个地址，计算机通过这个内存地址访问内存中的数据。</p><p id="33S6VFND">数组中由于内存是连续的，所以我们可以通过基地址直接计算出对应的下标所在的内存地址。数组中计算某个下标元素的内存地址公示如下：</p><p><blockquote id="33S6VFPM"><strong>a[i]_address = base_address + i * data_type_size</strong><br/></blockquote></p><p id="33S6VFNF">在本例子中，数组中存储的是int类型数据（js中数组每个元素大小可以不同，是做了特殊处理，js中具体数组在内存中如何存储待研究；</p><p id="33S6VFNG"><strong>data_type_size</strong>为4个字节，所以如果要获取下标为2的元素的地址，通过上面的公式计算就得到来内存地址为1008，由于只计算一次就能获取到准确的内存地址，所以访问数组中某个元素的时间复杂度为：</p><p id="33S6VFNL">低效的“插入”和“删除”</p><p id="33S6VFNM">为什么说数组的“插入”和“删除”操作很低效呢？我们知道数组在内存中是连续的，如果进行插入或者删除操作的话，由于数组要保证内存数据的连续性，所以数据需要进行移动，来保证连续性。</p><p id="33S6VFNN">下面举例说明：</p><p id="33S6VFNO"><strong>插入：</strong></p><p id="33S6VFNP"><strong>插入操作：</strong>假设数组的长度为n，现在，如果我们需要将一个数据插入到数组中的第k个位置。为了把第k个位置腾出来，给新来的数据，我们需要将第k~n这部分的元素都顺 序地往后挪一位。那插入操作的时间复杂度是多少呢?我们可以分析一下。</p><p id="33S6VFNQ"><strong>分析：</strong>如果第k个位置是数组末尾，那么不需要移动数据，此时最好时间复杂度为：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1019%2Fc9j00sllqdw0000d00017000qp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="33S6VFNU">如果在数组的开头插入数据，则所有的数据都要往后移动一位，所以最坏时间复杂度为：</p><p id="33S6VFO2">因为我们在每个位置插入的元素的概率是一样的，所以平均时间复杂度为：</p><p id="33S6VFO6">通过上面的分析我们看到，插入操作的平均时间复杂度为：</p><p id="33S6VFOA">那么有没有能够优化的地方呢？</p><p id="33S6VFOB">其实是有的，但是只能针对特定的情况进行优化。</p><p id="33S6VFOC">比如当数组仅仅作为存储数据的集合而不在乎存储的数据的顺序时，我们可以直接将第k个元素放在数组最后，将要插入的元素放在第k个位置。这样就能做到时间复杂度为</p><p id="33S6VFOG">但这也导致了快排是一个<strong>不稳定的</strong><strong>排序算法</strong></p><p id="33S6VFOH">举个例子来看一下上面的优化方式：假设数组a[10]中存储了如下5个元素:a，b，c，d，e。 我们现在需要将元素x插入到第3个位置。我们只需要将c放入到a[5]，将a[2]赋值为x即可。最后，数组中的元素如下: a，b，x，d，e，c。如下图所示：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1019%2Fbj00sllqe90007d000k0007mp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="33S6VFOL"><strong>删除：</strong></p><p id="33S6VFOM"><strong>删除操作：</strong>存在长度为n的数组，现在需要删除第k个元素，删除第k个元素后为了保证数组中第k个位置不出现空洞导致数组内存不连续，所以需要将k~n的元素都要向前移动一位。我们依旧分析一下时间删除操作的时间复杂度。</p><p id="33S6VFON"><strong>分析：</strong></p><p id="33S6VFOO">如果删除的是最后一个元素，则不需要移动，所以最好时间复杂度为：</p><p id="33S6VFOS">删除的是第一个元素，那么后面的k~n个元素都要向前移动一位，所以最坏时间复杂度为：</p><p id="33S6VFP0">在每个位置删除的概率是一样的，那么平均时间复杂度为：</p><p id="33S6VFP4">那么删除操作能否优化呢？</p><p id="33S6VFP5">其实也是可以的，我们通过上面的例子知道每删除一个元素就要移动后面的所有元素，那么我们能不能把多个删除操作放在一起，统一进行一次数据移动呢？</p><p id="33S6VFP6">举个例子来看一下上面的优化方式：数组a[10]中存储了8个元素:a，b，c，d，e，f，g，h。现在，我们要依次删除a，b，c三个元素。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1019%2F655b5955j00sllqek0006d000k00048p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="33S6VFPA">为了避免d,e,f,g,h这几个元素被移动三次，每次删除操作的时候并不去直接进行数据搬移，而是把要删除的元素标志为已删除，当数组中需要插入元素但是发现数组已经满了之后，再将标记为删除的元素真正的删除，这样就大大减少了删除操作导致的数据迁移。</p><p id="33S6VFPC">解答标题，为什么很多编程语言中数组下标都是从0开始</p><p id="33S6VFPD">我们之前有计算过数组的内存寻址公式 a[i]_address = base_address + i * data_type_size；</p><p id="33S6VFPE">如果从1开始的话，我们可以得到对应的内存寻址公式为 a[i]_address = base_address + (i - 1) * data_type_size，每次随机访问一个元素都多了一个减法操作。</p><p id="33S6VFPF">数组是一种很基础的数据结构，效率需要尽可能的高，所以为了减去一次减法操作，所以数组选择了从0开始编号而不是从1开始。</p><p id="33S6VFPG">当然也并不是非0不可，有的语言甚至支持负数的下标，例如python。但是大多数都是从0开始编号，可能也和C语言以0作为下标有关，后面的语言或多或少的都借鉴了C语言。</p><p id="33S6VFPI">总结</p><p id="33S6VFPJ">我们今天学习了数组。它可以说是最基础、最简单的数据结构了。</p><p id="33S6VFPK">数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为O(n)，我们也了解到了一维数组的寻址公式，和插入和删除操作的优化方法。</p>