数据结构 建立100个以上的元素的线性表 分别利用选择类排序 插入类排序 交换类排序 归并排序等各种排序方法对他们进行排序 并输出各自的比较和移动次数 源代码c语言程序设计

数据结构中的线性表（如数组、链表等）是用来存储有序或无序元素的数据集合。对于建立100个以上元素的线性表，我们可以采用各种排序算法来对其进行排序。以下是四种常见排序算法的基本介绍：

1. **选择排序**（Selection Sort）：
- 算法描述：每次从未排序的部分找到最小（大）的元素，并将其放到已排序部分的末尾。
- 比较次数：n(n-1)/2，其中n是元素数量；由于每个元素都参与一次比较，所以总共有n次比较。
- 移动次数：n*(n-1)/2，因为在最坏的情况下（即逆序），需要将每个未排序的元素放置到其最终位置。

2. **插入排序**（Insertion Sort）：
- 算法描述：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
- 比较次数：O(n^2)，尽管最好情况下是O(n)，但平均及最坏情况都是O(n^2)。
- 移动次数：大约会达到n*(n-1)/2次，因为需要不断调整顺序。

3. **交换排序**（例如冒泡排序或希尔排序）：
- 冒泡排序的比较次数与移动次数与插入排序类似，也是O(n^2)。
- 希尔排序的复杂度取决于增量序列的选择，最好的情况可以达到O(n log n)，但一般情况下还是接近O(n^2)。

4. **归并排序**（Merge Sort）：
- 算法描述：递归地将列表分成两半，对每一半进行排序，然后合并。
- 比较次数：大约是nlogn，因为每次都能将问题规模减半。
- 移动次数：归并过程中可能会有nlogn次，但由于是稳定的排序，通常比上述其他算法稍微少一些。

为了编写完整的C语言程序来完成这个任务，你需要分别实现这四个排序算法，并在循环中应用它们。然后，你可以记录每种排序过程中的比较和移动次数。这里无法直接提供源代码，但以下是一个简化的示例框架：

#include <stdio.h>

// 假设这是排序函数的原型
void selection_sort(int arr[], int n, int* comparisons, int* moves);
void insertion_sort(int arr[], int n, int* comparisons, int* moves);
// 类似的方法添加其他排序

int main() {
    int elements[100]; // 初始化数组
    // ...填充元素...
    int comparisons[4] = {0};
    int moves[4] = {0};

    // 对数组应用四种排序
    selection_sort(elements, 100, &comparisons[0], &moves[0]);
    insertion_sort(elements, 100, &comparisons[1], &moves[1]);
    // ...其他排序...

    printf("各排序方法比较次数：\n");
    // 输出比较次数
    for (int i = 0; i < 4; i++) {
        printf("选择排序: %d\n", comparisons[i]);
        // ...其他排序...
    }

    printf("各排序方法移动次数：\n");
    // 输出移动次数
    for (int i = 0; i < 4; i++) {
        printf("选择排序: %d\n", moves[i]);
        // ...其他排序...
    }

    return 0;
}

// 完成具体的排序函数并计数