本节书摘来自华章出版社《数据结构与算法：Python语言描述》一书中的第3章，第3.2节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看
3.2顺序表的实现
顺序表的基本实现方式很简单：表中元素顺序存放在一片足够大的连续存储区里，首元素（第一个元素）存入存储区的开始位置，其余元素依次顺序存放。元素之间的逻辑顺序关系通过元素在存储区里的物理位置表示（隐式表示元素间的关系）。
3.2.1基本实现方式
最常见情况是一个表里保存的元素类型相同，因此存储每个表元素所需的存储量相同，可以在表里等距安排同样大小的存储位置。这种安排可以直接映射到计算机内存和单元，表中任何元素位置的计算非常简单，存取操作可以在O(1) 时间内完成。
设有一个顺序表对象，其元素存储在一片元素存储区，该存储区的起始位置（内存地址）已知为l0。假定表元素编号从0开始（符合Python和许多编程语言的约定），元素e0自然应存储在内存位置Loc(e0)＝l0。再假定表中一个元素所需的存储单元数为c＝size（元素），在这种情况下，就有下面简单的元素ei的地址计算公式：
Loc(ei)＝Loc(e0)＋c×i
表元素的大小size(e) 通常可以静态确定（例如，元素是整数或实数，或包含一组大小确定的元素的复杂结构），在这种情况下，计算机硬件将能支持高效的表元素访问。另一方面，如果表中元素的大小有可能不同，也不难处理，只要略微改变顺序表的存储结构，就仍然可以保证O(1) 时间的元素访问操作（下面很快就会介绍）。
顺序表元素存储区的基本表示方式（布局）如图3.1a所示，元素的下标是其逻辑地址，可以用上面公式计算出其物理地址（实际地址）。根据前面有关计算机内存结构的讨论，元素访问是具有O(1) 复杂度的操作。
如果表元素的大小不统一，按照上面方案将元素顺序存入元素存储区，将无法通过统一公式计算元素位置。这时可以采用另一种布局方案，如图3.1b所示，将实际数据元素另行存储，在顺序表里各单元位置保存对相应元素的引用信息（链接）。由于每个链接所需的存储量相同，通过上述统一公式，可以计算出元素链接的存储位置，而后顺链接做一次间接访问，就能得到实际元素的数据了。注意，在图3.1b里的c不是数据元素的大小，而是存储一个链接所需的存储量，这个量通常很小。
在图3.1b所示的存储安排中，顺序表里保存的不是实际数据，而是找到实际数据的线索，这样的顺序表也被称为对实际数据的索引，这是最简单的索引结构，在后面章节里还会讨论其他更复杂的索引结构。
在确定了顺序表的基本表示方式之后，还需要进一步考虑线性表所需的各种操作的特点和需求，以及由它们带来的结构性问题。
线性表的一个重要性质是可以加入/删除元素，这也就是说，在一个表的存续期间，其长度（其中元素的个数）可能变化。这就带来了一个问题：在建立一个表时，应该安排多大的一块存储区？表元素存储块需要安排在计算机内存里，一旦分配就占据了内存里的一块区域，有了固定的大小（并因此确定了容量，即确定了元素个数的上限）。而且，该块的前后都可能被其他有用对象占据，存储块的大小不能随便变化，特别是无法扩充。
在建立一个顺序表时，一种可能是按建立时确定的元素个数分配存储。这种做法适合创建不变的顺序表，例如Python的tuple对象。如果考虑的是变动的表，就必须区分表中（当前的）元素个数和元素存储区的容量。在建立这种表时，一个合理的办法是分配一块足以容纳当前需要记录的元素的存储块，还应该保留一些空位，以满足增加元素的需要。
这样，在一个顺序表的元素存储区里，一般情况是保存着一些元素，还存在一些可以存放元素的空位。在这种情况下，需要约定元素的存放方式，通常把已有元素连续存放在存储区前面一段，空位都在后面。为了保证正确操作，就需要记录元素存储区的大小和当前的元素个数。这样，一个顺序表对象的完整信息如图3.2所示，这是一个具有可容纳8个元素的存储区，且当前存放了4个元素的顺序表。
易见：元素存储区的大小决定了表的容量，这是分配存储块时确定的，对于这个元素存储区，容量值保持不变。而元素个数的记录要与表中实际元素个数保持一致，在表元素变化时（加入或删除元素时），都需要更新这一记录。
3.2.2顺序表基本操作的实现
有了表容量和元素个数信息，表操作的实现方式已经很清楚了。下面假设用max表示表的容量，即可能容纳的最大元素个数，num表示当前元素个数。
创建和访问操作
创建空表：创建空表时，需要分配一块元素存储，记录表的容量并将元素计数值设置为0。图3.3表示一个容量为8的空表。注意，创建新表的存储区后，应立即将两个表信息记录域（max和num）设置好，保证这个表处于合法状态。
表的各种访问操作都很容易实现。
简单判断操作：判断表空或表满的操作很容易实现，即表空当且仅当num＝0，表满当且仅当num＝max。这两个简单操作的复杂度都是O(1)。
访问给定下标i的元素：访问表中第i个元素时，需要检查i的值是否在表的合法元素范围内，即0≤i≤num－1。超出范围的访问是非法访问。位置合法时需要算出元素的实际位置，由给定位置得到元素的值。显然，这个操作不依赖于表中元素个数，因此也是O(1) 操作。
遍历操作：要顺序访问表中元素，只需在遍历过程中用一个整数变量记录遍历达到的位置。每次访问表元素时，通过存储区开始位置和上述变量的值在O(1) 时间内可算出相应元素的位置，完成元素访问（取元素值或修改元素值）。找下一元素的操作就是加一，找前一元素的操作就是减一，遍历中要保证下标加一减一后的访问不超出合法范围。
查找给定元素d的（第一次出现的）位置：这种操作称为检索或查找（searching）。在没有其他信息的情况下，只能通过用d与表中元素逐个比较的方式实现检索，称为线性检索。这里需要用一个基于下标的循环，每步用d与当前下标的表元素比较。下标变量控制循环的范围，从0开始至等于表中的元素个数时结束。在找到元素时返回元素下标，找不到时可以返回一个特殊值（例如 －1，因为它不会是元素的下标，很容易判断）。
查找给定元素d在位置k之后的第一次出现的位置：与上面操作的实现方式类似，只是需要从k＋1位置的元素开始比较，而不是从位置0开始。
另一种需求与最后这两个操作类似：给定一个条件，要求找到第一个满足该条件的元素，或者某位置之后满足条件的下一个元素。条件可以是定义查找操作时确定的，更一般情况是允许在调用查找操作时提供一个描述条件的谓词函数。这两个操作的实现方式与上面两个操作类似，只是在其中不比较元素，而是检查条件是否成立。
最后几个操作都需要检查表元素的内容，属于基于内容的检索。数据存储和检索是一切计算和信息处理的基础，后面有关字典和检索的一章将深入研究这个问题。
总结一下：不修改表结构的操作只有两种模式，或者是直接访问，或者是基于一个整型变量，按下标循环并检查和处理。前一类操作都具有O(1) 的时间复杂度，后一类操作与访问的元素个数相关，复杂度为O(n)，这里的n是表中元素个数。
变动操作：加入元素
下面考虑表的变动操作，即各种加入和删除元素的操作。其中在表的尾端加入和删除操作的实现很简单，在其他位置加入和删除的操作麻烦一些。
加入元素的各种情况参看图3.4，假定是在前面图3.2所示的连续表状态下，以几种不同的方式加入一个新元素。
尾端加入新数据项：这种情况要求把新数据项存入当时表中的第一个空位，即下标num的位置。如果这时num＝max，即元素个数等于容量，表满了，操作就会失败（后面将介绍处理这种情况的其他技术）。如果表不满就直接存入元素，并更新表的元素计数值。显然，这是一个O(1) 操作。如果希望把元素简单地加入表中，没有其他要求，就应该采用尾端加入的方式，因为这样做操作最简单，效率最高。
图3.4a显示的是在图3.2的表尾端加入新元素111后的状态。
新数据存入元素存储区的第i个单元：这是一般情况，尾端加入是这里的特殊情况，即其中的i恰好等于num；首端加入也是它的特殊情况。在一般情况下，需要首先检查下标i是否为插入元素的合法位置，从下标0到num（包括num，如果表不满）都是合法位置。确定合法后就可以考虑插入了。通常情况下位置i已经有数据（除非i等于num），要把新数据存入这里，又不能简单抛弃原有的数据，就必须把该项数据移走。移动数据的方式需要根据操作的要求确定。此外，操作前也要检查表是否已满，操作结束后的状态还应该保持有数据的单元在存储区前段连续，以及num的正确更新。
如果操作不要求维持原有元素的相对位置（不要求保序），可以采用简单处理方式：把原来位于i的元素移到位置num，放到其他已有元素之后，腾出位置i放入新元素，最后把元素计数值num加一。这一操作仍能在O(1) 时间完成。图3.4b显示了在原表中位置1插入数据111后的状态，原来在位置1的693被移到位置4。
如果要求保持原有元素的顺序（保序），就不能像上面那样简单地腾出空位，必须把插入位置i之后的元素逐一下移，最后把数据项存入位置i。这样操作的开销与移动元素的个数成正比，一般而言受限于表中元素个数，最坏和平均情况都是O(n)。图3.4c描绘的是完成在位置1插入数据111并要求保序操作后的状态。
变动操作：删除元素
现在考虑元素删除操作。下面示例以图3.4c中的表为操作前的状态。
尾端删除数据：删除表尾元素的操作非常简单，只需将元素计数值num减一。这样，原来的表尾元素不再位于合法的表下标范围，相当于删除了。对于图3.4c的表，删除表尾元素后的状态如图3.5a所示，从逻辑上说，最后的154已经看不到了。
删除位置i的数据：这是一般的定位删除，尾端删除是其特殊情况，其中i恰好等于num－1。首端删除也是它的特殊情况。对一般情况，首先要检查下标i是否为当前表中合法的元素位置，合法位置是0≤i≤num－1。下标非法时可以采用引发异常的策略，也可以忽略它，什么也不做。确认下标合法后实际删除元素。
与加入元素的情况类似，这里也分为两种情况：如果没有保序要求，就可以简单处理，直接把当时位于num－1的数据项拷贝到位置i，覆盖原来的元素。如果有保序要求，就需要将位置i之后元素的数据逐项上移。删除后修改表的元素计数值。
图3.5b给出了在非保序方式下删除下标1元素的结果。同样，由于元素计数值减一，最后的154也不再会被访问了。图3.5c给出了删除同一个元素，但保持其他元素原有顺序的操作结果，这使顺序表回到了图3.2的状态。
显然，尾端删除和非保序定位删除操作的时间复杂度是O(1)，而保序定位删除的复杂度是O(n)，因为其中可能移动一系列元素。
基于条件的删除：这种删除操作不是给定被删元素的位置，而是给出需要删除的数据项d本身，或者是给出一个条件要求删除满足这个条件的（一个、几个或者所有）元素。显然，这种操作与前面讨论过的检索有关，需要找到元素后删除它或它们。
这种操作也需要通过循环实现，循环中逐个检查元素，查到要找的元素后删除。显然，一般而言，这类操作都是线性时间操作，复杂度为O(n)。
顺序表及其操作的性质
顺序表的一些操作比较简单，复杂度为常量的O(1)。下面想仔细地重新考虑定位加入和删除操作的复杂度，首端和尾端加入/删除是它们的特例。这里只考虑保序的操作，前面说过这一对操作的复杂度是O(n)，现在详细讨论这个问题。
假设给定的顺序表里有n个元素，在其中下标i的位置加入一项新数据，需要移动n－i个元素；而删除下标为i的数据项需要移动n－i－1个元素。再假设在位置i加入和删除元素的
概率分别是pi和pi′，不难看到：执行加入操作中平均的元素移动次数是，删除操作
的平均元素移动次数是。考虑平均复杂度时涉及各种情况的分布。作为最简
单的情况，假设在所有位置操作出现的概率相同，可以算出这两个操作的平均时间复杂度是O(n)。最坏情况的时间复杂度显然也是O(n)。
如前所说，各种访问操作，如果其执行中不需要扫描表内容的全部或者一部分，其时间复杂度都是O(1)，需要扫描表内容操作时间复杂度都是O(n)。后一种情况的例子如根据元素的值进行检索，遍历表中元素求出它们的和（如果元素是数值）等。
表的顺序实现（顺序表）的总结：
优点：O(1) 时间的（随机、直接的）按位置访问元素；元素在表里存储紧凑，除表元素存储区之外只需要O(1) 空间存放少量辅助信息。
缺点：需要连续的存储区存放表中的元素，如果表很大，就需要很大片的连续内存空间。一旦确定了存储块的大小，可容纳单元个数并不随着插入/删除操作的进行而变化。如果很大的存储区里只保存了少量数据项，就会有大量空闲单元，造成表内的存储浪费。另外，在执行加入或删除操作时，通常需要移动许多元素，效率低。最后，建立表时需要考虑元素存储区大小，而实际需求通常很难事先估计。
在下一小节里将会看到，最后这个“固定容量”的缺点实际上是可以解决的。
3.2.3顺序表的结构
从前面的讨论中已经看到，一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即那些有关表的整体情况的信息。根据前面的考虑，后一部分信息中包括元素存储区的容量和当前表中的元素个数两项。一个具体数据结构应该具有一个对象的整体形态。对于顺序表，就是要把上述两块信息关联起来，形成一个完整的对象。怎样把这两部分信息组织为一个顺序表的实际表示呢？这是实现顺序表时需要解决的第一个问题。
两种基本实现方式
由于表的全局信息只需要常量存储，对于不同的表，这部分的信息规模相同。根据计算机内存的特点，至少有两种可行表示方式，如图3.6所示。
在图3.6a所示的实现方式中，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，几部分数据的整体形成一个完整的表对象。这种一体式实现比较紧凑，有关信息集中在一起，整体性强，易于管理。另外，由于连续存放，从表对象L出发，根据下标访问元素，仍然可以用与前面类似的公式计算位置，只需加一个常量：
Loc(ei)＝Loc(L)＋C＋i×size(e)
其中C是数据成分max和num的存储量。
这种方式也有些缺点。例如，这里的元素存储区是表对象的一部分，因此不同的表对象大小不一。另一个问题是创建后元素存储区就固定了，参看下面的讨论。
图3.6b给出了另一种实现方式，其中表对象里只保存与整个表有关的信息（容量和元素个数），实际元素存放在另一个独立的元素存储区对象里，通过链接与基本表对象关联。这样表对象的大小统一，但不同表对象可以关联不同大小的元素存储区。这种实现的缺点是一个表通过多个（两个）独立的对象实现，创建和管理工作复杂一些。
采用后一种实现方式，基于下标的元素访问仍然可以在常量时间完成。有关操作要分为两步：首先从表对象找到元素存储区，而后用前面公式计算存储位置。显然，这一操作代价比一体式实现中的代价略高，但仍然只需常量时间。
替换元素存储区
分离式实现的最大优点是带来了一种新的可能：可以在标识不变的情况下，为表对象换一块元素存储区。也就是说，表还是原来的表，其内容可以不变，但是容量改变了。在实际使用中，如果不断向一个顺序表里加入元素，最终一定会填满其元素存储区。如果该表采用一体式实现方式，此时再向表中加入元素的操作就会失败。由于表对象安排在内存，它的两边可能有其他对象，一般而言，不可能直接扩大其存储。要想继续程序的工作，就只能另外创建一个容量更大的表对象，把元素搬过去。但这是一个新对象，要修改当时使用原对象的所有位置，使之改用新对象，这个任务通常很难完成。
如果采用分离式技术实现，问题就很容易解决了。这时可以在不改变对象的情况下换一块更大的元素存储区，使加入元素操作可以正常完成。操作过程如下：
1）另外申请一块更大的元素存储区。
2）把表中已有的元素复制到新存储区。
3）用新的元素存储区替换原来的元素存储区（改变表对象的元素区链接）。
4）实际加入新元素。
经过这几步操作，还是原来那个表对象，但其元素存储区可以容纳更多元素，而所有使用这个表的地方都不必修改。这样就做出了一种可扩充容量的表，只要程序的运行环境（计算机系统）还有空闲存储，这种表就不会因为满了而导致操作无法进行。人们也把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。
后端插入和存储区扩充
一个较大的顺序表，通常都是从空表或者很小的表出发，通过不断增加元素而构造起来的。如果在创建表的时候不能确定这个表的最终大小，又需要保证操作的正常进行，采用动态顺序表技术就是最合理的选择。这样的表能随着元素的加入动态变化，自动满足实际应用的需要。现在考虑这种表的增长过程的时间复杂度问题。
假设随着操作的进行，动态顺序表的大小从0逐渐扩大到n。如果采用前端插入或一般定位插入的方式加入数据项，每次操作的时间开销都与表长度有关，总时间开销应该与n的平方成正比，也就是说，整个增长过程的时间复杂度为O(n2)。
现在考虑后端插入。由于不需要移动元素，一次操作本身的复杂度是O(1)。但在这里还有一个情况需要考虑：在连续加入了一些数据项后，表的当前元素存储区终将被填满，这时就需要换一块存储区。更换存储区时需要复制表中的元素，整个复制需要O(m) 时间（其中m是当时的元素个数）。这样就出现了一个问题，即应该怎样选择新存储区的大小呢？这件事牵涉到空闲存储单元的量和替换存储的频度问题。
考虑一种简单策略：每次替换存储时增加10个元素存储位置。这种策略可称为线性增长，10是增长的参数。假设表长（表中元素个数）从0不断增长到1000，每加入10个元素就要换一次存储，复制当时的所有元素。总的元素复制次数是：
对一般的n，很容易算出总的元素复制次数大约是1/20×n2。也就是说，虽然每次做尾端插入的代价是O(1)，加上元素复制之后，一般而言，执行一次插入操作的平均代价还是达到了O(n)。虽然这里出现的是一个分数因子，但结果还是不理想。
容易想到，这里总操作开销比较高，是因为在不断插入元素的过程中频繁替换元素存储区，而且每次替换复制的元素越来越多。修改替换时增加的空位数，例如把10改成100，只能减小n2的常量系数，不能带来本质的改进。应该考虑一种策略，其中随着元素数量的增加，替换存储区的频率不断降低。人们提出的一种策略是每次容量加倍。
假设表元素个数从0增加到1024，存储区大小的序列是1, 2, 4, 8, …, 1024，表增长过程中复制元素的次数是：
其中9＝log21024―1。对一般的n，在整个表的增长过程中，元素复制次数也是O(n)。也就是说，采用存储增长的加倍策略和尾端插入操作，将一个表从0增长到n，插入操作的平均时间复杂度是O(1)。不同替换策略带来了大不相同的操作复杂度。
请注意，后一个策略在操作复杂度上有明显优势，但也付出了代价。考虑在上面两种不同策略下，连续加入元素的增长过程：对于前一策略，无论n取什么值，元素存储区的最大空闲单元数是9；而对于后一种策略，空闲单元可以达到差不多n/2。也就是说，为获得时间上的优势，在这里需要付出空间代价。
还有一个问题值得注意：动态顺序表后端插入的代价不统一，大多数可以在O(1) 时间完成，但也会因为替换存储区而出现高代价操作。当然，高代价操作的出现很偶然，并将随着表的增大而变得越来越稀疏。另一方面，不间断地插入元素是这里的最坏情况，一般情况下插入和删除操作交替出现，替换存储区的情况会更稀少。但无论如何，高代价操作是可能出现的，应该注意这一情况，特别是在开发时间要求特别高的应用时。
缓解上述问题的一种可能性是增加一个设定容量的操作。这样，如果程序员知道下面一段操作的时间要求必须得到保证，就可以在操作前根据情况把表设定（修改）到一个足够大的容量，保证在关键计算片段中不会出现存储区替换。
3.2.4Python的list
前几小节介绍了顺序表的各方面情况和实现技术。由于本书使用Python，这里不准备给出在Python里定义顺序表的实际代码，因为Python的list和tuple就采用了顺序表的实现技术，具有前面讨论的顺序表的所有性质。本小节介绍这方面情况，以帮助学习者进一步理解Python的这两种类型，知道如何正确合理地使用它们。
tuple是不变的表，因此不支持改变其内部状态的任何操作。在其他方面，它与list的性质类似。因此，下面将集中关注list的情况。
list的基本实现技术
Python标准类型list就是一种元素个数可变的线性表，可以加入和删除元素，在各种操作中维持已有元素的顺序。其重要的实现约束还有：
基于下标（位置）的高效元素访问和更新，时间复杂度应该是O(1)。
允许任意加入元素（不会出现由于表满而无法加入新元素的情况），而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。
这些基本约束决定了list的可能解决方案：
由于要求O(1)时间的元素访问，并能维持元素的顺序，这种表只能采用连续表技术，表中元素保存在一块连续存储区里。
要求能容纳任意多的元素，就必须能更换元素存储区。要想在更换存储区时list对象的标识（id）不变，只能采用分离式实现技术。
在Python的官方实现中，list就是一种采用分离式技术实现的动态顺序表，其性质都源于这种实现方式。Python的list采用了前面介绍的元素存储区调整策略，如果需要反复加入元素，用lst.insert(len(lst),x)比在一般位置插入的效率高。Python提供了另一等价写法lst.append(x)，如果合适就应优先选用。
在Python的官方系统中，list实现采用了如下的实际策略：在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append等）时，如果元素区满就换一块4倍大的存储区。但如果当时的表已经很大，系统将改变策略，换存储区时容量加倍。这里的“很大”是一个实现确定的参数，目前的值是50000。引入后一个策略是为了避免出现过多空闲的存储位置。如前所述，通过这套技术实现的list，尾端加入元素操作的平均时间复杂度是O(1)。
一些主要操作的性质
list结构的其他特点也由其顺序表实现方式决定。例如，由于其中一般位置的插入和删除操作都是保序的，要移动一些表元素，因此需要O(n) 时间。在其他位置加入元素时也要检查存储区是否已满，如果满了就需要换一块存储，把原有元素复制过去。这些操作可以优化，例如在复制元素的过程中完成新元素加入。
再看其他操作的情况。对那些所有序列（无论是否变动序列）都有的共性操作，复杂度由操作中需要考察的元素个数确定。
len(.) 是O(1) 操作，因为表中必须记录元素个数，自然可以简单地取用。
元素访问和赋值，尾端加入和尾端删除（包括尾端切片删除）都是O(1) 操作。
一般位置的元素加入、切片替换、切片删除、表拼接（extend）等都是O(n) 操作。pop操作默认为删除表尾元素并将其返回，时间复杂度为O(1)，一般情况的pop操作（指定非尾端位置）为O(n) 时间复杂度。
Python的一个问题是没有提供检查一个list对象的当前存储块容量的操作，也没有设置容量的操作，一切与容量有关的处理都由Python解释器自动完成。这样做的优点是降低编程负担，避免了人为操作可能引进的错误。但这种设计也限制了表的使用方式，前面提出的策略在这里也难以使用了。
几个操作
下面考察list的几个特殊操作。
lst.clear() 清除表lst的所有元素，这应该是一个O(1) 操作，但具体实现的情况未见说明。有两种明显的可行做法：
简单地将表lst的元素计数值（表的长度记录）设置为0。这样元素存储区里的所有元素都看不见了，自然应该看作空表。
另行分配一个空表用的存储区，原存储区直接丢弃。Python解释器的存储管理器将自动回收这个存储块（可能在将来某个时候）。
第一种实现最简单，操作效率高，但不能真正释放元素存储区占用的存储。如果在执行clear之前这个表很长，执行操作后表里已经没有元素了，但仍占用原有的大块存储。第二种实现是再次从空表开始，如果这个表再增长到很大，过程中又要一次次更换存储区。
语句lst.reverse() 修改表lst自身，将其元素顺序倒置，原来的首元素变成尾元素，其他元素的情况类似。很容易做出下面的实现（假设它定义在list类里，并假设元素存储区的域名为elements）。显然，这个操作的复杂度是O(n)。
def reverse(self):
elems = self.elements
I, j = 0, len(elems)-1
while i < j:
elems[i], elems[j] = elems[j], elems[i]
i, j = i+1, j-1
标准类型list仅有的特殊操作（一个对象方法）是sort，它对表中元素排序。这是一个变动操作，操作中移动表存储区里的元素。有关算法问题在第9章讨论。最好的排序算法的平均和最坏情况时间复杂度都是O(n log n)。Python的排序算法就是这样。
3.2.5顺序表的简单总结
顺序结构（技术）是组织一组元素的最重要方式。在顺序表结构中，直接采用顺序结构实现线性表，这种结构（技术）也是许多其他数据结构的实现基础。在后面章节里将会反复看到这方面的实例。
采用顺序表结构实现线性表：
最重要特点（优势）是O(1) 时间的定位元素访问。很多简单操作的效率也比较高。
这里最重要的麻烦是加入/删除等操作的效率问题。这类操作改变表中元素序列的结构，是典型的变动操作。由于元素在顺序表的存储区里连续排列，加入/删除操作有可能要移动很多元素，操作代价高。
只有特殊的尾端插入/删除操作具有O(1) 时间复杂度。但插入操作复杂度还受到元素存储区固定大小的限制。通过适当的（加倍）存储区扩充策略，一系列尾端插入可以达到O(1) 的平均复杂度。
顺序表的优点和缺点都在于其元素存储的集中方式和连续性。从缺点看，这样的表结构不够灵活，不容易调整和变化。如果在一个表的使用中需要经常修改结构，用顺序表去实现就不太方便，反复操作的代价可能很高。
还有一个问题也值得提出：如果程序里需要巨大的线性表，采用顺序表实现就需要巨大块的连续存储空间，这也可能造成存储管理方面的困难。
下一节中讨论的链接表在这两个方面都有优势。
