【例2.1】 将顺序表（a1, a2, …, an）重新排列为以a1为界的两部分：a1前面的值均比a1小、a1后面的值均比a1大（这里假设数据元素的类型具有可比性，不妨设为整型），操作前后如图所示。这一操作称为划分，a1称为基准。
划分的方法有多种，下面介绍的划分算法思路简单，但性能较差。
基本思路：从第二个元素开始到最后一个元素，逐一向后扫描。
（1）当前数据元素ai比a1大时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个。

图2.5 顺序表的划分
（2）若当前元素若比a1小，说明它应该在a1的前面，此时将它上面的元素依次向下移动一个位置，然后将它置于最上方。
顺序表的划分算法：

void partition (SeqList *L)
{ int i，j；
datatype x，y；
x=L->data[0]； / * 将基准置入 x 中 */
for (i=1；i<=L->last；i++)
if (L->data[i]<x) / * 当前元素小于基准 * /
{ y=L->data[i]；
for (j=i-1；j>=0；j- -) / * 移动 */
L－>data[j+1]=L->data[j]；
L->data[0]=y；
}
}
【例2.2】 设有顺序表A和B，其元素均按从小到大的顺序升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也从小到大升序排列。
算法思路：依次扫描A和B的元素，比较A、B当前的元素的值，将值较小的元素赋给C，如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下部分赋给C即可。C的容量要能够容纳A、B两个线性表长度的和。
有序表的合并算法：

void merge (SeqList A, SeqList B, SeqList *C)
{ int i，j，k；
i=0；j=0；k=0；
while ( i<=A.last && j<=B.last )
if (A.data[i]<B.data[j])
C->data[k++]=A.data[i++]；
else
C->data[k++]=B.data[j++]；
while (i<=A.last )
C->data[k++]= A.data[i++]；
while (j<=B.last )
C->data[k++]=B.data[j++]；
C->last=k-1；
}
算法的时间复杂度是O(m+n)，其中m是A的表长，n是B的表长。
【例2.3】 两个线性表的比较操作。假定两个线性表的比较方法如下：设A、B是两个线性表，表长分别为m和n。A′和B′分别为A和B中除去最大共同前缀后的子表。
例如，A=(x, y, y, z, x, z)，B=(x, y, y, z, y, x, x, z)，两表最大共同前缀为（x, y, y, z）。则A′=(x, z)，B′=(y, x, x, z)。
若A′=B′=空表，则A=B。若A′=空表且B′ ≠空表，或两者均不为空表且A′的首元素小于B′的首元素，则A<B；否则，A>B。
算法思路：首先找出A、B的最大共同前缀；然后求出A′和B′，再按比较规则进行比较，A>B函数返回1；A=B返回0；A<B返回-1。
两个顺序表的比较算法：

int compare( A, B, m, n)
int A[ ]，B[ ]；
int m，n；
{ int i=0, j，AS[ ]，BS[ ]，ms=0，ns=0； /AS, BS作为A′, B′/
while (A[i]B[i]) i++； /* 找最大共同前缀*/
for (j=i；j<m；j++)
{ AS[j-i]=A[j]； ms++； } /* 求A′, ms为A′的长度*/
for (j=i；j<n；j++)
{ BS[j-i]=B[j]； ns++； } /* 求B′, ns为B′的长度*/
if (msns&&ms0) return 0；
else if (ms0&&ns>0 || ms>0 && ns>0 && AS[0]<BS[0]) return -1；
else return 1；
}
算法的时间复杂度是O(m+n)