1）编写直接插入排序算法，分析算法的复杂性。 （2）编写冒泡排序算法，分析算法的复杂性。 （3）编写快速排序算法，分折算法的复杂性。 （4）编写堆选排序算法。 （5）设计菜单，以选择菜单方式进行操作，并实现上述算法。

好的，我可以为您提供这些算法的代码示例和分析。

1. 直接插入排序算法

直接插入排序算法的基本思想是将待排序的元素插入到已排序的序列中，形成一个新的有序序列。

代码示例：

void insertSort(int arr[], int n) {
    int i, j;
    int temp;
    for (i = 1; i < n; i++) {
        temp = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

算法的复杂度分析：

- 最好情况：当数组已经有序时，时间复杂度为 O(n)。
- 最坏情况：当数组逆序排列时，时间复杂度为 O(n^2)。
- 平均情况：时间复杂度为 O(n^2)。

2. 冒泡排序算法

冒泡排序算法的基本思想是通过相邻元素之间的比较和交换，将待排序的元素逐步移动到正确的位置。

代码示例：

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

算法的复杂度分析：

- 最好情况：当数组已经有序时，时间复杂度为 O(n)。
- 最坏情况：当数组逆序排列时，时间复杂度为 O(n^2)。
- 平均情况：时间复杂度为 O(n^2)。

3. 快速排序算法

快速排序算法的基本思想是通过选取一个基准元素，将待排序的元素分成左右两个子序列，然后对左右子序列进行递归排序。

代码示例：

void quickSort(int arr[], int left, int right) {
    int i, j, temp, pivot;
    if (left >= right) {
        return;
    }
    pivot = arr[left];
    i = left;
    j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] < pivot) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

算法的复杂度分析：

- 最好情况：每次划分都划分为长度相等的两个子序列，时间复杂度为 O(nlogn)。
- 最坏情况：每次划分都划分为长度为 1 和 n-1 的两个子序列，时间复杂度为 O(n^2)。
- 平均情况：时间复杂度为 O(nlogn)。

4. 堆选排序算法

堆选排序算法的基本思想是将待排序的元素构建成一个大根堆或小根堆，然后依次取出堆顶元素并调整堆，直到所有元素都被取出。

代码示例：

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int temp;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    int i, temp;
    for (i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (i = n - 1; i >= 0; i--) {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

算法的复杂度分析：

- 最好情况：每次调整堆的时间复杂度为 O(logn)，总时间复杂度为 O(nlogn)。
- 最坏情况：每次调整堆的时间复杂度为 O(logn)，总时间复杂度为 O(nlogn)。
- 平均情况：时间复杂度为 O(nlogn)。

5. 菜单选择方式进行操作

代码示例：

#include <stdio.h>

void insertSort(int arr[], int n);
void bubbleSort(int arr[], int n);
void quickSort(int arr[], int left, int right);
void heapSort(int arr[], int n);

int main() {
    int arr[100];
    int n, i, choice;

    printf("请输入数组长度：");
    scanf("%d", &n);

    printf("请输入数组元素：");
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    printf("请选择排序算法：\n");
    printf("1. 直接插入排序\n");
    printf("2. 冒泡排序\n");
    printf("3. 快速排序\n");
    printf("4. 堆选排序\n");
    printf("请输入您的选择：");
    scanf("%d", &choice);

    switch (choice) {
        case 1:
            insertSort(arr, n);
            break;
        case 2:
            bubbleSort(arr, n);
            break;
        case 3:
            quickSort(arr, 0, n - 1);
            break;
        case 4:
            heapSort(arr, n);
            break;
        default:
            printf("无效的选择。\n");
            return 0;
    }

    printf("排序结果为：\n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

void insertSort(int arr[], int n) {
    // 直接插入排序代码
}

void bubbleSort(int arr[], int n) {
    // 冒泡排序代码
}

void quickSort(int arr[], int left, int right) {
    // 快速排序代码
}

void heapSort(int arr[], int n) {
    // 堆选排序代码
}

以上代码实现了一个菜单选择方式进行排序的程序。用户可以根据菜单选择需要使用的排序算法。