19335074_黄玟瑜_hw41

【知识点详解】 1. **计数排序(Counting Sort)**: 计数排序是一种非基于比较的排序算法，特别适用于整数排序。其基本思想是通过统计数组中每个元素出现的次数，然后根据这些计数将元素放到正确的位置上。在最佳情况下，计数排序的时间复杂度为Ο(n+k)，其中n是数组元素个数，k是整数的范围。它比任何比较排序算法都快，但需要额外的空间来存储计数值。 2. **并行编程**: 这个实验中使用了OpenMP（Open Multi-Processing）来实现并行版本的计数排序。OpenMP是一种应用编程接口（API），用于支持共享内存并行计算，允许程序员在多核处理器或多处理器系统上编写并行程序。 3. **OpenMP关键指令**: `#pragma omp parallel num_threads(thread_count)` 是OpenMP的关键字，用于声明并行区域，并指定使用thread_count个线程来执行后续代码。这里的`num_threads`可以用来控制并行执行的线程数量。 4. **线程分配**: 在实验代码中，`int my_n = n / thread_count;` 计算了每个线程需要处理的元素个数，`int my_rank = omp_get_thread_num();` 获取当前线程的编号，`int my_first_i = my_n * my_rank;` 和 `int my_last_i = my_first_i + my_n;` 分别确定了每个线程处理的数组元素范围。 5. **线程安全**: 由于各个线程写入的是不同位置的`temp`数组，所以这里不存在数据竞争问题，实现了并行处理。每个线程负责更新自己负责范围内元素的计数，并将元素放到`temp`数组的相应位置。 6. **内存管理**: 使用`malloc()`分配了与原数组大小相同的临时数组`temp`，用于存储排序后的结果。排序完成后，用`memcpy()`将`temp`的内容复制回原数组`a`，最后使用`free(temp)`释放动态分配的内存。 7. **优化并行性能**: 在实际应用中，为了进一步提高并行效率，可以考虑负载均衡，确保每个线程处理的任务大致相等。如果数组元素分布不均匀，可能会导致某些线程较早完成工作，而其他线程还在忙碌，这可以通过动态调整线程的工作负载或者使用更复杂的分块策略来解决。 8. **保持原有顺序**: 在计数排序中，当有相等的元素时，`else if (a[j] == a[i] && j < i)`这一条件用于保证原始数组中相等元素的相对顺序不变。这是因为在写回结果时，先处理的元素会被写入更靠前的位置。 这个实验通过OpenMP实现了一个并行版本的计数排序，利用多线程将原本串行的计数过程分担到多个处理器上，从而提高了排序的效率。同时，实验也关注了线程安全和数据一致性，以及如何保持相等元素的原始顺序。