我目前正在开发一个同时对字符串进行排序的程序。我的程序接收一个文件，将文件的每一行读入一个数组，并将字符串数组拆分为更小的字符串数组。然后，程序为每个较小的数组启动一个线程，并对它们进行快速排序。一旦每个线程完成对其数组的排序，主线程就会从线程对象收集所有结果。然后应该将较小的、现已排序的数组合并为一个大的、已排序的数组。
我知道我的快速排序实现是有效的——程序使用一个线程对单词进行排序。我需要的是一种将线程返回的数组嵌套在一起的算法。
如有任何帮助，我们将不胜感激——提前致谢。
从决赛开始merge的程序归并排序 https://en.wikipedia.org/wiki/Merge_sort。您读取每个 m 数组的第一个值（单个子数组的最小值），然后选择 m 个读取值中的最小值（全局最小值），将其推入结果中，然后从包含的数组中删除它或增加各自的索引加一。然后，迭代直到所有子数组都为空，或者所有索引都到达相应数组的末尾。
注意：如果您有一个非常大的数据集（它实际上用于处理这种情况），这可能会减少内存使用量，但由于分割成本（如果您复制子数组，则它会变成线性）和原始快速排序的性能可能会比原始快速排序差多线程开销。请考虑，当应用于大型数组时，就地合并排序会更节省空间。还要考虑一下，谁编写了您正在使用的快速排序，可能花了时间优化调用和分支执行。
这是基本的理论 CS，但请注意，您不能简单地通过使用并行性来降低计算复杂度，您只能得到一个线性加速度。最后，快速排序恰好达到了比较排序算法的平均复杂度下限：如果您想超越快速排序O(nlog(n))我有坏消息要告诉你。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
