数据结构 已知长度为n的顺序表L，其数据元素类型为整型，设计一个时间复杂度为O(n)、空间复杂度为O(1)的算法，将L中所有小于k的整数放在表的前半部分，大于等于k的整数放在后半部分。请用C语言实现

在C语言中，可以使用双指针法来实现这个任务，同时满足O(n)的时间复杂度和O(1)的空间复杂度要求。以下是算法步骤和代码实现：

1. 定义两个指针，`left`指向数组的开始位置，`right`指向数组的结束位置。
2. 当`left`小于`right`时，继续循环：
- 如果`L[left]`小于`k`，则交换`left`和`left+1`处的元素，然后`left++`。
- 否则，如果`L[right]`大于等于`k`，则不做操作，直接`right--`。
3. 循环结束后，数组就按照要求分为了两部分。

#include <stdio.h>

void partition(int L[], int n, int k) {
    int left = 0; // 指向小于k的元素
    int right = n - 1; // 指向大于等于k的元素

    while (left < right) {
        if (L[left] < k) { // 小于k，将左指针的元素向右移动
            int temp = L[left];
            L[left++] = L[right]; // 交换
            L[right--] = temp;
        } else {
            left++; // 不小于k，左指针右移
        }
    }
}

int main() {
    int L[] = {1, 5, 3, 8, 4, 7, 6, 2}; // 测试数组
    int n = sizeof(L) / sizeof(L[0]);
    int k = 5;

    partition(L, n, k);

    printf("分割后的数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", L[i]);
    }

    return 0;
}