1． 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

### 回答1：
可以使用快排的思想来解决这个问题。首先选取第一个关键字作为划分关键字，然后从两端向中间扫描，找到第一个大于等于划分关键字的元素和第一个小于划分关键字的元素并交换位置，直到两端扫描的指针相遇为止。此时，线性表左半部分的元素都小于划分关键字，右半部分的元素都大于等于划分关键字。时间复杂度为O(n)。

具体实现方法如下：

1. 设置两个指针left和right，初始时left指向线性表的第一个元素，right指向最后一个元素。
2. 比较left指向的元素和划分关键字的大小关系，若小于划分关键字，则left指针向右移动一位；否则，继续执行步骤3。
3. 比较right指向的元素和划分关键字的大小关系，若大于等于划分关键字，则right指针向左移动一位；否则，继续执行步骤4。
4. 交换left指向的元素和right指向的元素的位置。
5. 重复步骤2-4，直到left和right指针相遇为止。

例如，对于线性表[3,1,5,7,2,4]，

### 回答2：
可以使用快速排序的思想来设计该算法。

首先，选取序列中的一个关键字Ki作为基准值，然后从序列的第一个元素K1开始，逐个比较K1与Ki的大小关系。如果K1小于Ki，则放入左半部分，否则放入右半部分。然后再从序列的第二个元素K2开始，继续进行比较，并按照大小关系放入相应的部分。如此循环直到最后一个元素Kn。

通过上述步骤，我们将整个序列划分为左半部分和右半部分。

该算法的时间复杂度为O(n)，因为需要遍历整个序列一次，对每个元素进行比较和放入相应的部分。假设序列的长度为n，则最坏情况下需要进行n次比较和n次放入，总共执行2n次操作，时间复杂度为O(n)。

需要注意的是，选取基准值Ki的选择会影响算法的效率。如果选择的基准值正好是序列的中位数，那么能够达到最理想的时间复杂度O(n)。但是在一般情况下，选择基准值的方法可以是随机选择、取首、中、尾元素的中位数等。

### 回答3：
一个简单的算法可以实现要求。首先将第一个关键字作为比较基准(Ki)，然后使用两个指针left和right分别指向线性表的头部和尾部。

接下来，我们进行如下的操作：
1. 从头部开始，逐步向右移动left指针直到找到第一个大于等于Ki的关键字。
2. 从尾部开始，逐步向左移动right指针直到找到第一个小于Ki的关键字。
3. 如果此时left指针仍然在right指针的左侧，交换left和right指针所指向的关键字。
4. 重复上述操作，直到left指针不再小于等于right指针。

最终，在执行完上述操作后，线性表将被划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

由于每次操作都会移动左右指针至少一次，所以整个算法的时间复杂度为O(n)。

以下是算法的示例代码：

def partition(arr, n):
    left = 0
    right = n-1
    pivot = arr[0]
    
    while left <= right:
        while left <= right and arr[left] < pivot:
            left += 1
        while left <= right and arr[right] >= pivot:
            right -= 1
        
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    
    return left-1

arr = [K1, K2, ..., Kn]  # 初始记录关键字序列
n = len(arr)

pivot_index = partition(arr, n)

print("左半部分的关键字序列:", arr[:pivot_index+1])
print("右半部分的关键字序列:", arr[pivot_index+1:])

注意：示例代码中的arr、n和pivot_index分别表示初始记录关键字序列、关键字序列的长度和分割点的索引。