多线程｜sort.c 多线程排序

1.题目要求

多线程排序

主线程创建两个辅助线程
辅助线程1使用选择排序算法对数组的前半部分排序
辅助线程2使用选择排序算法对数组的后半部分排序
主线程等待辅助线程运行结束后,使用归并排序算法归并子线程的计算结果
本题要求 1: 使用线程参数，消除程序中的代码重复

2.解决思路

创建辅助线程等整体的思路与上一题相同，关键在于实现选择排序算法与归并排序算法。

选择排序算法的思想是：如果有N个元素需要排序，首先从N个元素中找到最小的那个元素，然后与起始索引位置上的元素进行交换(如果没有比原来起始索引位置上的元素小就不用交换)，接着再从剩下的N-1个元素中找出最小的元素，再与起始索引+1位置上的元素进行交换；之后，再从剩下的N-2个元素中找出最小的元素，再与起始索引+2位置上的元素进行交换……重复上面的操作，一直到排序完成为止。

归并排序算法的思想是：分而治之的思想，每个递归过程涉及三个步骤：第一，分解：把待排序的 n 个元素的序列分解成两个子序列，每个子序列包括 n/2 个元素；第二，治理：对每个子序列分别调用归并排序merge_sort，进行递归操作；第三，合并：调用子函数merge合并两个排好序的子序列，生成排序结果。

3.代码

#include 
#include 
#include 
#include 
#include 


#define N 10  // 数组元素个数

struct param {
  int *array;
  int start;
  int end;
};


// 使用选择排序算法对给定范围的数组排序
void *compute(void *arg) {
  struct param *param = (struct param *)arg;
  int i, j, min, index, temp;

  for(i = param->start; i <= param->end; i++) {
    printf("%d ", param->array[i]);
  }

  for(i = param->start; i < param->end; i++) {
    min = param->array[i];
    index = i;
    for(j = i; j <= param->end; j++) {
      if(param->array[j] < min) {
        min = param->array[j];
        index = j;
      }
    }
    if(i != index) {
      temp = param->array[i];
      param->array[i] = param->array[index];
      param->array[index] = temp;
    }
  }

  printf(" ->  ");
  for(i = param->start; i <= param->end; i++) {
    printf("%d ", param->array[i]);
  }
  printf("n");
  return NULL;
}

// 有序的 s[begins...ends] 和 s[begins+1...endt] -> 有序的 t[begins...endt]
void merge(int *s, int *t, int begins, int ends, int endt) {
  int i, j, k;
  for(i = begins, j = ends + 1, k = begins; i <= ends && j <= endt;) {
    if(s[i] <= s[j]) 
      t[k++] = s[i++];
    else
      t[k++] = s[j++];
  }
  if(i <= ends) {
    while (i <= ends) 
      t[k++] = s[i++];
  }
  if(j <= endt) {
    while (j <= endt) 
      t[k++] = s[j++];
  }
}

// 使用归并排序算法归并子线程的计算结果
// s[begin...end] -> t[begin...end]
void merge_sort(int *s, int *t, int begin, int end) {
  int *t2 = malloc(sizeof(t));
  if(begin == end) {
    t[begin] = s[begin];
  }
  else {
    int mid = (begin + end) / 2;
    merge_sort(s, t2, begin, mid);
    merge_sort(s, t2, mid + 1, end);
    merge(t2, t, begin, mid, end);
  }
}


int main() {
  pthread_t workers[2];
  struct param params[2];
  int array[N + 1], i;
  int *sorted_array = malloc(sizeof(array));

  srand(time(NULL));
  for(i = 1; i <= N; i++) {
    array[i] = rand() % 100 + 1;
  }

  printf("随机生成长度为 %d 的数组:n", N);
  for(i = 1; i <= N; i++) {
    printf("%d ", array[i]);
  }
  printf("nn");

  for(i = 0; i < 2; i++) {
    struct param *param = ¶ms[i];
    param->array = array;
    param->start = i * (N / 2) + 1;
    param->end = (i + 1) * (N / 2);
    pthread_create(&workers[i], NULL, compute, param);
  }

  for(i = 0; i < 2; i++) {
    pthread_join(workers[i], NULL);
  }

  merge_sort(array, sorted_array, 1, N);
  memcpy(array + 1, sorted_array + 1, sizeof(array));

  printf("n按从小到大次序排序后的数组:n");
  for(i = 1; i <= N; i++) {
    printf("%d ", array[i]);
  }
  printf("nn");

  return 0;
}

4.运行结果

$ gcc sort.c -lpthread
$ ./a.out 
随机生成长度为 10 的数组:
68 30 72 95 77 37 82 65 10 99 

68 30 72 95 77  ->  30 68 72 77 95 
37 82 65 10 99  ->  10 37 65 82 99 

按从小到大次序排序后的数组:
10 30 37 65 68 72 77 82 95 99

多线程｜sort.c 多线程排序

C/C++/C#相关栏目本月热门文章