我目前正在开发一个程序来同时对字符串进行排序。我的程序接收一个文件，将文件的每一行读入一个数组，然后将字符串数组拆分为更小的字符串数组。然后程序为每个较小的数组启动一个线程，并对它们进行快速排序。一旦每个线程完成对其数组的排序，主线程就会从线程对象中收集所有结果。然后应该将较小的、现已排序的数组合并为一个大的、排序的数组。
我知道我的快速排序实现有效——程序使用一个线程对单词进行排序。我需要的是一种将线程返回的数组嵌套在一起的算法。
感谢任何帮助 - 提前致谢。
最佳答案
从mergesort 的最后一个merge 过程开始.您读取每个 m 数组的第一个值(单个子数组的最小值)，然后选择 m 读取值中的最小值(全局最小值)，将其插入结果并将其从包含数组中删除或递增各自的指数加一。然后，迭代直到所有子数组都为空，或者所有索引都到达各自数组的末尾。
注意:如果你有一个非常大的数据集(它实际上用于处理这种情况)，这可能会减少内存使用，但由于拆分成本(如果你复制子数组，它会变成线性) 和多线程开销。考虑到当应用于大型数组时，inplace Mergesort 更节省空间。还要考虑一下，您正在使用的快速排序的编写者可能花时间优化调用和分支执行。
这是基本的理论 CS，但请注意，您不能简单地通过使用并行来降低计算复杂度等级，您只能获得线性加速。最后，Quicksort 碰巧达到了比较排序算法的平均复杂度的下限:如果你想超越 Quicksort O(nlog(n)) 我有个坏消息要告诉你。
关于java - Java 中的并发排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16398338/