本关任务：请编写一个算法函数void partion（sequence list *L），尽可能快地将顺序表L中的所有奇数调整到表的左边，所有偶数调整到表的有边，并分析算法的时间复杂度。 测试输入：5 12345 预期输出：15342

要编写一个算法函数`partion`，我们可以采用双指针的方法，一个指针i从左开始扫描，另一个指针j从右开始扫描。当找到一个偶数（列表左侧）或奇数（列表右侧）时，交换它们的位置。这样可以保证奇数始终出现在左侧，偶数出现在右侧。

以下是该算法的伪代码：

function partition(L, length):
    i = 0  // 左侧指针，指向偶数
    j = length - 1 // 右侧指针，指向奇数

    while i < j:
        // 当左侧遇到奇数或右侧遇到偶数时交换位置
        if L[i] % 2 == 1 and i != j:
            swap(L[i], L[j])
            j -= 1
        else if L[j] % 2 == 0:
            i += 1

    return L

对于给定的输入 `5` 和 `12345`，这个函数会返回 `15342`，因为所有的奇数1、3、5被移动到了左边，偶数2、4留在了右边。

时间复杂度分析：
- 这个算法遍历了整个列表一次。对于长度为 n 的列表，`i` 和 `j` 各走了 n 步，所以总步数为 2n。因此，时间复杂度是 O(n)。

相关问题

请编写一个算法函数void partion(sequence_list *L)，尽可能快地将顺序表L中的所有奇数调整到表的左边，所有偶数调整到表的右边，并分析算法的时间复杂度。

首先，我们可以创建一个名为`partition_sequence`的函数，它接受一个指向顺序表的指针`sequence_list *L`作为输入。我们将采用双指针技术，一个从左向右遍历寻找偶数并将它们移动到右侧，另一个从右向左遍历寻找奇数并将其移到左侧。

// 假设 sequence_list 类包含一个整数元素的成员变量
class sequence_list {
public:
    int data;
    // 其他成员和操作忽略
};

void partition_sequence(sequence_list* L, int length) {
    if (length <= 1) return; // 如果列表为空或只有一个元素，无需分区

    int left = 0, right = length - 1; // 左指针和右指针初始位置
    while (left < right) {
        // 右指针寻找第一个偶数
        while (right > 0 && L[right].data % 2 != 0) right--;
        // 左指针寻找第一个奇数
        while (left < right && L[left].data % 2 == 0) left++;

        // 交换左右两侧找到的第一个数字
        if (left < right) {
            std::swap(L[left], L[right]);
        }
    }
}

时间复杂度分析：
这个算法的时间复杂度是O(N)，其中N是列表的长度。因为每个元素最多只会被访问一次（左指针和右指针各走一半），所以总的比较和交换次数都是线性的。

请编写一个算法函数void partion（sequence_list*L），尽可能快地将顺序表L中的所有奇数调整到表的左边，所有偶数调整到表的右边，并分析算法的时间复杂度。

这是一个经典的排序算法问题，可以使用双指针法来解决，即一个指针i从左向右扫描，另一个指针j从右向左扫描。当找到第一个偶数时，我们将j指向的偶数移动到i+1的位置，然后继续向左移动i；同时，如果i遇到奇数，则不动，直到找到下一个偶数。当两个指针相遇时，我们就完成了任务，因为左侧都是奇数，右侧都是偶数。

以下是该算法的伪代码：

void partition(sequence_list *L) {
    int i = 0, j = L->length - 1;
    while (i < j) {
        // 找到左侧的第一个偶数
        while (i < j && L->data[i] % 2 != 0) {
            i++;
        }
        // 将偶数移到右侧
        if (i < j) {
            swap(&L->data[i], &L->data[j]);
            j--;
        }

        // 找到右侧的第一个奇数（如果有的话）
        while (i < j && L->data[j] % 2 == 0) {
            j--;
        }
        // 如果左侧有奇数则不动
    }
}

时间复杂度分析：在这个算法中，每次循环i都会向前推进一位，最坏的情况下需要遍历整个序列，所以时间复杂度是O(n)，其中n是列表的长度。空间复杂度为O(1)，因为我们只用到了常数级别的额外空间。