随机数排序

使用并行或者串行排序，对随机数进行排序，测试速度

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

#define MAX_THREADS 4 // 定义最大线程数

typedef struct {
    int *array;
    int size;
} Randnum;

typedef struct {
    Randnum *randnum;
    int start;
    int end;
} ThreadData;

void generate_random_numbers(Randnum *randnum, int count) {
    randnum->array = (int *)malloc(count * sizeof(int));
    randnum->size = count;
    for (int i = 0; i < count; ++i) {
        randnum->array[i] = rand() % 10000;
    }
}

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

void merge_sorted_arrays(int *array, int start1, int end1, int start2, int end2) {
    int *temp = (int *)malloc((end2 - start1) * sizeof(int));
    int i = start1, j = start2, k = 0;
    while (i < end1 && j < end2) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    while (i < end1) {
        temp[k++] = array[i++];
    }
    while (j < end2) {
        temp[k++] = array[j++];
    }
    for (i = start1, k = 0; i < end2; ++i, ++k) {
        array[i] = temp[k];
    }
    free(temp);
}

void *thread_sort(void *arg) {
    ThreadData *data = (ThreadData *)arg;
    qsort(data->randnum->array + data->start, data->end - data->start, sizeof(int), compare);
    pthread_exit(NULL);
}

int main() {
    srand(time(NULL));

    int num_count;
    printf("请输入要生成的随机数的数量: ");
    scanf("%d", &num_count);

    Randnum randnum;
    generate_random_numbers(&randnum, num_count);

    int mid = num_count / 2;

    clock_t start_time = clock();

    pthread_t threads[MAX_THREADS]; // 声明线程数组
    ThreadData data[MAX_THREADS];   // 声明线程参数数组

    int chunk_size = num_count / MAX_THREADS; // 计算每个线程处理的数据块大小
    for (int i = 0; i < MAX_THREADS; ++i) {
        data[i].randnum = &randnum;
        data[i].start = i * chunk_size;
        data[i].end = (i == MAX_THREADS - 1) ? num_count : (i + 1) * chunk_size;

        pthread_create(&threads[i], NULL, thread_sort, &data[i]); // 创建线程
    }

    for (int i = 0; i < MAX_THREADS; ++i) {
        pthread_join(threads[i], NULL); // 等待线程结束
    }

    for (int i = 1; i < MAX_THREADS; ++i) {
        merge_sorted_arrays(randnum.array, 0, i * chunk_size, i * chunk_size, num_count); // 合并各个线程排序后的子数组
    }

    clock_t end_time = clock();
    double execution_time = (double)(end_time - start_time) / CLOCKS_PER_SEC;
    printf("并行排序时间: %f 秒\n", execution_time);

    // 串行排序
    memcpy(randnum.array, randnum.array, num_count * sizeof(int)); // 恢复原始数据
    start_time = clock();
    qsort(randnum.array, num_count, sizeof(int), compare); // 调用标准库的快速排序函数进行串行排序
    end_time = clock();
    execution_time = (double)(end_time - start_time) / CLOCKS_PER_SEC;
    printf("串行排序时间: %f 秒\n", execution_time);

    free(randnum.array);

    return 0;
}