1.输入10个有序的整数关键字，利用折半查找法，查找用户输入的关键字。 2.试以单链表为存储结构，实现简单的选择排序算法。代码和数据分析和算法分析

1. 折半查找法

折半查找法，也称二分查找，是一种高效的查找算法。前提是数组中的元素必须是有序的。其基本思想是将查找区域分为两半，每次比较中间元素，缩小查找范围，最终找到目标元素或者不存在。

代码如下：

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[10] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int key;
    printf("请输入要查找的数：");
    scanf("%d", &key);
    int index = binarySearch(arr, 10, key);
    if (index == -1) {
        printf("未找到\n");
    } else {
        printf("找到了，下标为%d\n", index);
    }
    return 0;
}

算法分析：

时间复杂度：O(log n)
空间复杂度：O(1)

2. 单链表实现选择排序

选择排序是一种简单直观的排序算法，基本思想是每次从待排序的元素中选择最小的元素，放到已排序的末尾。

代码如下：

#include <stdio.h>
#include <stdlib.h>

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

void insert(Node **head, int data) {
    Node *newNode = (Node *) malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node *p = *head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = newNode;
    }
}

void display(Node *head) {
    Node *p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void selectionSort(Node *head) {
    Node *p = head;
    while (p != NULL) {
        Node *q = p->next;
        while (q != NULL) {
            if (q->data < p->data) {
                int tmp = p->data;
                p->data = q->data;
                q->data = tmp;
            }
            q = q->next;
        }
        p = p->next;
    }
}

int main() {
    Node *head = NULL;
    insert(&head, 3);
    insert(&head, 1);
    insert(&head, 4);
    insert(&head, 2);
    insert(&head, 5);
    printf("排序前：");
    display(head);
    selectionSort(head);
    printf("排序后：");
    display(head);
    return 0;
}

算法分析：

时间复杂度：O(n^2)
空间复杂度：O(1)

虽然选择排序的时间复杂度较高，但是它的代码简单易懂，实现起来也比较容易。在数据规模较小的情况下，选择排序的效率还是比较高的。