类型1：多个有序顺序表
← 内容总览 03 / 24 下一节 → 原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 类型1：多个有序顺序表
这是多指针法最经典的应用场景。通过在每个有序表上设置一个指针（可能在头或尾），并根据特定规则移动它们，可以高效地解决多种问题。我们从以下题目中感受：
例题2-2：给定升序数组A、B，长度分别为n、m，合并成一个新的升序数组C并输出。
例如： A = {1， 2， 7} ， B = {3， 4， 5} 。
枚举法：最暴力的枚举是，为了确定新数组 C 的下一个元素，我们需要比较 A 和 B 中还剩下的所有元素，然后找出最小的。确定第二个元素时，又要重复这个过程。这显然是低效的，时间复杂度为O((m+n)²)。
多指针法：在枚举法的基础上，发现升序条件没有用到，数组A、B、C都会是升序数组，因此数组C的下一个元素一定是数组A中最小元素及数组B中最小元素其中较小的那个。最小元素在升序数组中是最左侧元素，所以设置两个指针分别指向A、B现存最小元素，每次比较指针所指元素并移动即可，时间复杂度O(m+n)。
• 分析：数组C 需要是升序，元素是从小到大存放，下一个元素一定是数组A 中最小元素及数组B 中最小元素其中较小的那个。所以每个数组的指针都应该分别指向他们还未处理的最小元素（即最左侧的下标）。
• 起始位置：数组A、B、C的指针都是从左侧开始向右移动。
• 规则：比较数组A、B对应指针所指的元素，将较小的元素复制到结果数组中，然后将该较小元素所在的数组的指针、最终数组的指针各移动一位。不断重复这个过程。这个规则保证了结果数组始终是升序的，因为我们每次都选取了当前所有待选元素中的最小值。
• 停止处理：当其中一个数组的指针移出数组（即遍历完该数组的所有元素）时，退出循环。此时，另一个数组中可能还有剩余的元素，由于原数组是有序的，这些剩余元素必然都大于等于已合并的所有元素。因此，只需将这个数组的剩余部分依次复制到结果数组的末尾即可。
void Merge ( int A [], int n , int B [], int m )
{
int C [ n + m ];
int i = 0 , j = 0 , k = 0 ;
}
//直到有一个数组遍历完退出循环
while ( i & lt ; n & amp ; & amp ; j & lt ; m )
if ( A [ i ] & lt ; B [ j ])
c [ k ++ ] = A [ i ++ ];
else
c [ k ++ ] = B [ j ++ ];
// 复制 A 中剩余的元素
while ( i & lt ; n )
c [ k ++ ] = A [ i ++ ];
// 复制 B 中剩余的元素
while ( j & lt ; m )
c [ k ++ ] = B [ j ++ ];
从左到右输出数组 C 中的元素
例如 : A = { -4 , -2 } B = { 0 , 1 , 3 } → C = { 16 , 9 , 4 , 1 , 0 } 。
void mergeAndSquare ( int A [], int n , int B [], int m )
{
int C [ n + m ];
int i = 0 , j = m - 1 , k = 0 ;
while ( i & lt ; n & amp ; & amp ; j & gt ; = 0 )
{
if ( abs ( A [ i ]) & gt ; abs ( B [ j ]))
{
C [ k ++ ] = A [ i ] * A [ i ];
i ++ ;
}
else
{
C [ k ++ ] = B [ j ] * B [ j ];
j -- ;
}
}
while ( i & lt ; n )
{
C [ k ++ ] = A [ i ] * A [ i ];
i ++ ;
}
while ( j & gt ; = 0 )
{
C [ k ++ ] = B [ j ] * B [ j ];
j -- ;
}
// 输出 C
}
例如 ： A = { -4 , -2 , 0 , 1 , 3 } → B = { 16 , 9 , 4 , 1 , 0 } 。
void squareAndSort ( int A [], int n )
{
int B [ n ];
int i = 0 , j = n - 1 , k = 0 ;
while ( i & lt ; = j )
{
if ( abs ( A [ i ]) & gt ; abs ( A [ j ]))
{
B [ k ++ ] = A [ i ] * A [ i ];
i ++ ;
}
else
{
B [ k ++ ] = A [ j ] * A [ j ];
j -- ;
}
}
// 输出 B
}
例题2 -9 ( 按 A [ 0 ] 划分 ) 的解法就是快排的单趟 Partition 。
例题2 -10 ( 划分为大小两半 ) 的解法 , 则是在 Partition 思想的基础上 , 不断调整 , 直到基准 pivot 的最终
位置恰好是 n / 2 。 这被称为 快速选择 ( Quick Select ) // 算法。
快速排序 ( Quick Sort ) vs . 快速选择 ( Quick Select )
{
• 目标不同 ： 快排的目标是整个数组有序 ; 快选的目标是找到第k小的元素 。
• 递归方式不同 ：
void ans ( int A [], int n )
{
int i = 0 , j = n - 1 ; // i和j是左右两个数组下标移动
int pivot = A [ 0 ];
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ j ] & gt ; = pivot ) j -- ;
while ( i & lt ; j & amp ; & amp ; A [ i ] & lt ; = pivot ) i ++ ;
if ( i & lt ; j ) swap ( A [ i ], A [ j ]); // A[j]<pivot, A[i]>pivot，交换
}
swap ( A [ 0 ], A [ i ]); // 将基准值放入他的最终位置
}
void ans ( int A [], int n )
{
int L = 0 , R = n - 1 ; // L和R是当前处理区间的左右边界
while ( true )
{
int i = L , j = R ;
int pivot = A [ L ];
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ j ] & gt ; = pivot ) j -- ;
while ( i & lt ; j & amp ; & amp ; A [ i ] & lt ; = pivot ) i ++ ;
if ( i & lt ; j ) swap ( A [ i ], A [ j ]);
}
swap ( A [ L ], A [ i ]);
if ( i == n / 2 ) return ;
if ( i & lt ; n / 2 ) L = i + 1 ; // 继续处理右区间
else R = i - 1 ; // 继续处理左区间
}
}
← 内容总览 03 / 24 下一节 →