设一组初始记录关键字序列(K1,K2,..,K)，要求设计一个算法能够在O(n)的时间复杂度内将线性表划分为两部分，其中左半部分的每个关键字均小于K1，右半部分的每个关键字均大于等于K1。用c语言写，时间复杂度只能是o（n）

这个问题可以使用双指针法来解决，同时维护两个指针i和j，分别指向数组的开始和结束。我们遍历数组，当遇到的元素大于等于K1时，我们将元素交换到数组的右侧，并将j指针向右移动一位。这个过程保证了左侧所有元素都小于K1，而右侧所有元素至少有一个大于等于K1。

以下是C语言的一个简单实现：

#include <stdio.h>

void partition(int arr[], int n, int k1) {
    int i = 0, j = n - 1;

    while (i <= j) {
        // 如果左侧指针指向的元素小于k1
        if (arr[i] < k1) {
            i++;
        }
        // 如果右侧指针指向的元素大于等于k1
        else if (arr[j] >= k1) {
            j--;
            // 交换左右两侧的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        } else {
            i++; // 如果两边都不满足条件，先移动左侧指针
        }
    }
}

// 测试函数
int main() {
    int arr[] = {1, 5, 9, 4, 8, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k1 = 5;
    partition(arr, n, k1);

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

    return 0;
}

这个算法的时间复杂度确实是O(n)，因为我们只遍历了一次数组。