26-数据结构-顺序表1

1. 合并两个有序顺序表为一个新的有序顺序表

函数原型：

cpp

复制编辑

void mergeArray(SeqList &L, SeqList &L1, SeqList &L2);

功能说明：
将两个递增有序顺序表 L1 和 L2 合并成一个新的递增有序顺序表 L，并返回结果表。

算法思路：

• 使用双指针分别遍历两个顺序表。

• 按照大小顺序插入新表中，保持递增有序。

• 最后将未合并的剩余部分依次插入新表。

---

2. 删除有序顺序表中所有值重复的元素

函数原型：

cpp

复制编辑

void deleteRepeatElem(SeqList &L);

功能说明：
删除顺序表中所有值重复的元素，仅保留唯一值。

适用条件：
顺序表为有序表（相同元素连续）。

算法思路：

• 使用快慢指针遍历数组。

• 如果当前 fast 与 slow 指向的值相等，则跳过重复项。

• 否则，将当前 fast 元素赋值给 slow + 1，并更新 slow。

• 最后更新表长。

---

3. 将顺序表中所有负数放在非负数前面（不要求顺序）

函数原型：

cpp

复制编辑

void reOrderArray(SeqList &L);

功能说明：
重新排列顺序表，使得所有负数元素位于非负数元素之前。

算法思路：

• 快慢指针遍历顺序表。

• 遇到负数时，将其与 slow 指向的位置交换，并将 slow 后移。

• 这样能在一次遍历中完成负数前移操作，时间复杂度为 O(n)。

---

4. 将顺序表划分为左右两部分，满足左半部分所有值 < Ki，右半部分所有值 > Ki

函数原型：

cpp

复制编辑

void sortKeylist(SeqList &L);

功能说明：
将表中元素以某个关键字 Ki 为界进行划分，使得所有 < Ki 的元素在左侧，所有 > Ki 的元素在右侧。这里默认 Ki 是第一个元素。

算法思路：

• 以 data[0] 为基准值。

• 用两个指针遍历，如果当前值小于基准值，则交换至左侧，并移动分界指针。

• 单趟遍历实现分割，时间复杂度为 O(n)。

---

总结

功能名称	方法名	时间复杂度	空间复杂度	特点
有序表合并	mergeArray	O(n)	O(1)	需要两个有序顺序表
删除重复元素	deleteRepeatElem	O(n)	O(1)	适用于有序表
负数前移	reOrderArray	O(n)	O(1)	原地交换，保持稳定性可改
关键字划分	sortKeylist	O(n)	O(1)	单次遍历实现原地划分