linux下利用pthread做多线程归并排序教程

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

typedef struct ThreadData {
    int start, end;//待排序的范围
    int* array;//数组指针
    int length;//数组的长度
}ThreadData;

//函数原型声明
void p_mergeSort(ThreadData* data);
void merge(int array[], int length, int left, int m, int right);
void mergeSort(int array[], int length, int start, int end);

//方便pthread_create调用，和mergesort之间做一个接口
void p_mergeSort(ThreadData* data)
{
    mergeSort(data->array, data->length, data->start, data->end);
}

// 归并排序中的合并算法
void merge(int array[], int length, int left, int m, int right)
{
    int* temp = (int*)malloc(sizeof(int) * length);
    int i, j, k;
    i = left;
    j = m + 1;
    k = 0;

    for (; i <= m && j <= right;) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++];
        }
        else {
            temp[k++] = array[j++];
        }
    }
    while (i <= m) {
        temp[k++] = array[i++];
    }
    while (j <= m) {
        temp[k++] = array[j++];
    }
    k = 0;
    for (i = left; i <= right; i++) {
        array[i] = temp[k++];
    }
    free(temp);
}

// 归并排序
void mergeSort(int array[], int length, int start, int end)
{
    if (start < end) {
        int i;
        pthread_t tid1, tid2;
        ThreadData data_left, data_right;
        i = (end + start) / 2;

        data_left.array = array;
        data_left.length = length;
        data_left.start = start;
        data_left.end = i;

        data_right.array = array;
        data_right.length = length;
        data_right.start = i+1;
        data_right.end = end;

        // 启动2个线程分别对左右两部分进行mergeSort
        pthread_create(&tid1, NULL, (void*)p_mergeSort, (void*)& data_left);
        pthread_create(&tid2, NULL, (void*)p_mergeSort, (void*)& data_right);
        pthread_join(tid1, NULL);
        pthread_join(tid2, NULL);
        // join等待完成后，再merge
        merge(array, length, start, i, end);
    }
}

int main() {
    pthread_t tid;
    int ret;

    int array[] = {9,8,7,6,5,4,3,2,1,0};

    ThreadData data;
    data.array = array;
    data.start = 0;
    data.end = 9;
    data.length = 10;

    ret = pthread_create(&tid, NULL, (void*)p_mergeSort, (void*)&data);
    if (ret) {
        printf("Thread Create Error\n");
        exit(0);
    }

    pthread_join(tid, NULL);

    for (int i = 0; i < 10; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    printf("Main Ends\n");

    return 0;
}

编译命令:

gcc sort.c -o a -lpthread

运行结果:

• 点赞
• 收藏
• 分享

• 文章举报

李先生i发布了10 篇原创文章 · 获赞 9 · 访问量 5653 私信 关注