C语言使用顺序表实现折半插入排序法，并在主函数中输入元素，再输出排序结果

在C语言中，顺序表通常使用数组结构来实现。对于折半插入排序（也称为二分查找插入），我们首先需要创建一个动态大小的数组来存储数据。以下是简单的步骤：

1. 定义一个结构体表示顺序表节点，包含数据域和指向下一个节点的指针。

typedef struct Node {
    int data;
    struct Node* next;
} ListNode;

2. 创建顺序表结构体并初始化头指针。

ListNode* list = NULL;

3. 主函数中，用户输入元素并添加到列表中，这里假设`getInput()`函数用于获取用户输入。

void insertHalfSort(int input) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = input;

    if (!list || newNode->data <= list->data) {
        newNode->next = list;
        list = newNode;
    } else {
        ListNode* temp = list;
        while (temp->next && temp->next->data < newNode->data) {
            temp = temp->next;
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

4. 插入所有元素后，进行折半插入排序。由于数组排序效率更高，我们可以直接遍历整个数组进行插入操作。

void sortList() {
    for (int i = 1; i < listSize; ++i) {
        ListNode* current = list;
        ListNode* target = list + i;
        
        // 如果目标位置比当前元素大，说明插入位置在其右侧
        while (current != NULL && target->data > current->data) {
            ListNode* temp = current;
            current = current->next;
        }

        // 移动元素
        if (current != NULL) {
            target->next = current->next;
        } else {
            list = target;
        }
        temp->next = target;
    }
}

// 假设listSize是一个全局变量，表示列表长度
void main() {
    int n;
    printf("Enter the number of elements: ");
    scanf("%d", &n);

    listSize = n;
    for (int i = 0; i < n; ++i) {
        insertHalfSort(getInput());
    }

    // 打印排序后的列表
    printList(list);
}

5. `printList()`函数用于遍历并打印顺序表，这里省略了，可以自定义实现。