1）（随机）生成两个十万个整数的数据文件File.txt和SortedFile.txt。SortedFile是File的数据排序后的文件。 2）读取上述文件进行排序，观察在最好、最坏和平均情况下快速排序的运行时间，并和归并排序时间比较。 3）读取上述文件的数据，设计在平均和最坏情况下的O(n)选择算法 。用c语言

好的，您的问题是关于文件排序和算法设计的，需要用C语言实现。我会尽力解答。

1. 文件排序

生成两个十万个整数的数据文件File.txt和SortedFile.txt，可以使用随机数生成器来生成随机数，并将其写入文件。然后可以使用排序算法对其进行排序。

对于快速排序和归并排序，最好的情况是输入数据已经是有序的，时间复杂度为O(nlogn)；最坏的情况是输入数据是逆序的，时间复杂度为O(n^2)；平均情况下时间复杂度为O(nlogn)。

我们可以使用C语言代码来实现：

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

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void merge_sort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        merge_sort(arr, l, m);
        merge_sort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int n = 100000;
    int arr[n];
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100000 + 1;
    }

    // 写入文件
    FILE* fp = fopen("File.txt", "w");
    for (int i = 0; i < n; i++) {
        fprintf(fp, "%d\n", arr[i]);
    }
    fclose(fp);

    // 快速排序
    clock_t start, end;
    start = clock();
    quick_sort(arr, 0, n - 1);
    end = clock();
    printf("快速排序时间: %f秒\n", (double)(end - start) / CLOCKS_PER_SEC);

    // 归并排序
    fp = fopen("File.txt", "r");
    for (int i = 0; i < n; i++) {
        fscanf(fp, "%d", &arr[i]);
    }
    fclose(fp);
    start = clock();
    merge_sort(arr, 0, n - 1);
    end = clock();
    printf("归并排序时间: %f秒\n", (double)(end - start) / CLOCKS_PER_SEC);

    return 0;
}

2. 排序算法的运行时间

我们可以使用相同的方法来测试快速排序和归并排序在最好、最坏和平均情况下的运行时间。

3. O(n)选择算法的设计

在平均和最坏情况下的O(n)选择算法是快速选择算法。快速选择算法和快速排序算法类似，只不过它只需找到第k小的元素即可，不需要对整个数组进行排序。

下面是快速选择算法的C语言代码：

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

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

int quick_select(int arr[], int low, int high, int k) {
    if (low == high) {
        return arr[low];
    }
    int pi = partition(arr, low, high);
    int length = pi - low + 1;
    if (k == length) {
        return arr[pi];
    }
    else if (k < length) {
        return quick_select(arr, low, pi - 1, k);
    }
    else {
        return quick_select(arr, pi + 1, high, k - length);
    }
}

int main() {
    int n = 100000;
    int arr[n];
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100000 + 1;
    }

    // 写入文件
    FILE* fp = fopen("File.txt", "w");
    for (int i = 0; i < n; i++) {
        fprintf(fp, "%d\n", arr[i]);
    }
    fclose(fp);

    // 快速选择算法
    fp = fopen("File.txt", "r");
    for (int i = 0; i < n; i++) {
        fscanf(fp, "%d", &arr[i]);
    }
    fclose(fp);
    int k = 50000;
    clock_t start, end;
    start = clock();
    int res = quick_select(arr, 0, n - 1, k);
    end = clock();
    printf("第%d小的数是%d，运行时间为%f秒\n", k, res, (double)(end - start) / CLOCKS_PER_SEC);

    return 0;
}

以上就是对您提出的问题的解答了，希望能对您有所帮助。