编写程序实现简单选择排序、堆排序（或归并排序），进行比较分析。用c语言实现

以下是C语言实现简单选择排序和堆排序的代码：

#include <stdio.h>

// 简单选择排序
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    for (i = 0; i < n-1; i++) {
        minIndex = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

// 堆排序
void heapSort(int arr[], int n) {
    int i, temp;
    // 建堆
    for (i = n/2-1; i >= 0; i--) {
        adjustHeap(arr, i, n);
    }
    // 排序
    for (i = n-1; i > 0; i--) {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        adjustHeap(arr, 0, i);
    }
}

// 调整堆
void adjustHeap(int arr[], int i, int n) {
    int j, temp;
    temp = arr[i];
    for (j = 2*i+1; j < n; j = 2*j+1) {
        if (j+1 < n && arr[j+1] > arr[j]) {
            j++;
        }
        if (temp >= arr[j]) {
            break;
        }
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = temp;
}

int main() {
    int arr1[] = {5, 2, 7, 1, 3, 6, 4};
    int arr2[] = {5, 2, 7, 1, 3, 6, 4};
    int n = sizeof(arr1) / sizeof(arr1[0]);

    selectionSort(arr1, n);
    printf("简单选择排序结果：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr1[i]);
    }

    heapSort(arr2, n);
    printf("\n堆排序结果：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr2[i]);
    }
    return 0;
}

我们可以通过比较简单选择排序和堆排序的运行时间来分析它们的效率。可以使用time.h头文件中的clock()函数来计算程序执行的时间。

下面是对比简单选择排序和堆排序的运行时间的代码：

#include <stdio.h>
#include <time.h>

// 简单选择排序
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    for (i = 0; i < n-1; i++) {
        minIndex = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

// 堆排序
void heapSort(int arr[], int n) {
    int i, temp;
    // 建堆
    for (i = n/2-1; i >= 0; i--) {
        adjustHeap(arr, i, n);
    }
    // 排序
    for (i = n-1; i > 0; i--) {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        adjustHeap(arr, 0, i);
    }
}

// 调整堆
void adjustHeap(int arr[], int i, int n) {
    int j, temp;
    temp = arr[i];
    for (j = 2*i+1; j < n; j = 2*j+1) {
        if (j+1 < n && arr[j+1] > arr[j]) {
            j++;
        }
        if (temp >= arr[j]) {
            break;
        }
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = temp;
}

int main() {
    int arr1[10000];
    int arr2[10000];
    int n = sizeof(arr1) / sizeof(arr1[0]);

    // 生成随机数组
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr1[i] = rand();
        arr2[i] = arr1[i];
    }

    // 计算简单选择排序的运行时间
    clock_t start1 = clock();
    selectionSort(arr1, n);
    clock_t end1 = clock();
    double time1 = (double)(end1 - start1) / CLOCKS_PER_SEC;
    printf("简单选择排序运行时间：%f秒\n", time1);

    // 计算堆排序的运行时间
    clock_t start2 = clock();
    heapSort(arr2, n);
    clock_t end2 = clock();
    double time2 = (double)(end2 - start2) / CLOCKS_PER_SEC;
    printf("堆排序运行时间：%f秒\n", time2);
    return 0;
}

通过运行不同大小的随机数组，可以得到堆排序的运行时间明显优于简单选择排序。这是因为堆排序使用了堆这种数据结构，可以快速找到最大值或最小值，从而减少了比较和交换的次数，提高了排序的效率。