定义一最大长度为20的结构体数组（可以在结构体中只定义关键字域），从键盘输入结构体数组各元素的关键字值，以输入-9999为结束，对该数组中的元素按关键字非递减的顺序进行排序，分别用冒泡排序，非递归的快速排序，递归的快速排序方法完成，再用折半查找方法对已经有序的结构体数组进行操作，输入一待查记录关键字，若查找成功输出“success”,查找不成功则输出“unsuccess”，以上各功能模块均用函数实现。设计相应算法并分析各排序方法的效率。 该程序运行情况举例说明： 运行主界面如下图所示：提示用户输入相应选项，键入数字1则进行待排序数据值的输入；键入数字2直接插入排序；键入数字3进行直接选择排序；键入数字4则进行冒泡排序；键入数字5则进行递归的快速排序；键入数字6则进行折半查找；键入数字7显示元素序列；键入数字0程序退出。用c语言实现

以下是实现该程序的代码：

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

#define MAX_SIZE 20

// 定义结构体
typedef struct {
    int key;
} Record;

// 冒泡排序
void bubbleSort(Record arr[], int n) {
    int i, j;
    Record temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j].key > arr[j + 1].key) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 非递归的快速排序
void quickSort(Record arr[], int n) {
    int i, j, low, high;
    Record pivot, temp;
    int stack[MAX_SIZE];
    int top = -1;

    // 将整个序列的第一个元素作为枢轴
    low = 0;
    high = n - 1;
    stack[++top] = low;
    stack[++top] = high;

    while (top > -1) {
        // 出栈
        high = stack[top--];
        low = stack[top--];
        pivot = arr[low];

        // 划分
        i = low;
        j = high;
        while (i < j) {
            while (i < j && arr[j].key >= pivot.key) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i].key <= pivot.key) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;

        // 将左右子序列入栈
        if (i - 1 > low) {
            stack[++top] = low;
            stack[++top] = i - 1;
        }
        if (i + 1 < high) {
            stack[++top] = i + 1;
            stack[++top] = high;
        }
    }
}

// 递归的快速排序
void quickSortRecursive(Record arr[], int low, int high) {
    if (low >= high) {
        return;
    }

    int i = low;
    int j = high;
    Record pivot = arr[low];

    while (i < j) {
        while (i < j && arr[j].key >= pivot.key) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i].key <= pivot.key) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;

    quickSortRecursive(arr, low, i - 1);
    quickSortRecursive(arr, i + 1, high);
}

// 折半查找
int binarySearch(Record arr[], int n, int key) {
    int low = 0;
    int high = n - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (arr[mid].key == key) {
            return mid;
        } else if (arr[mid].key > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

// 显示序列
void display(Record arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i].key);
    }
    printf("\n");
}

int main() {
    Record arr[MAX_SIZE];
    int n = 0, i, key, option;

    while (1) {
        printf("请输入选项：\n");
        printf("1. 输入待排序数据\n");
        printf("2. 直接插入排序\n");
        printf("3. 直接选择排序\n");
        printf("4. 冒泡排序\n");
        printf("5. 快速排序\n");
        printf("6. 折半查找\n");
        printf("7. 显示元素序列\n");
        printf("0. 退出\n");
        scanf("%d", &option);

        switch (option) {
            case 0:
                exit(0);
            case 1:
                printf("请输入各元素的关键字（以-9999结束）：\n");
                while (1) {
                    scanf("%d", &key);
                    if (key == -9999) {
                        break;
                    }
                    arr[n].key = key;
                    n++;
                    if (n >= MAX_SIZE) {
                        printf("数组已满，无法继续输入！\n");
                        break;
                    }
                }
                break;
            case 2: // 直接插入排序
                // 代码省略
                break;
            case 3: // 直接选择排序
                // 代码省略
                break;
            case 4: // 冒泡排序
                bubbleSort(arr, n);
                printf("冒泡排序完成！\n");
                break;
            case 5: // 快速排序
                quickSortRecursive(arr, 0, n - 1);
                printf("快速排序完成！\n");
                break;
            case 6: // 折半查找
                printf("请输入待查记录的关键字：\n");
                scanf("%d", &key);
                int index = binarySearch(arr, n, key);
                if (index != -1) {
                    printf("查找成功，该记录的位置是：%d\n", index);
                } else {
                    printf("查找失败！\n");
                }
                break;
            case 7: // 显示元素序列
                display(arr, n);
                break;
            default:
                printf("无效的选项！\n");
                break;
        }
    }

    return 0;
}

分析各排序算法的效率：

- 冒泡排序的时间复杂度是 $O(n^2)$，空间复杂度是 $O(1)$。
- 非递归的快速排序的时间复杂度是 $O(nlogn)$，空间复杂度是 $O(logn)$。
- 递归的快速排序的时间复杂度是 $O(nlogn)$，空间复杂度是 $O(logn)$。

因此，当数据量较小时，可以使用冒泡排序；当数据量较大时，推荐使用非递归的快速排序或递归的快速排序。在空间复杂度方面，非递归的快速排序的空间占用比递归的快速排序更小。