如何在java中使用N个线程对M个数组进行排序？
如何在java中使用N个线程对M个数组进行排序？
提问于 2010-10-29 03:43:40
我必须使用N(i=1..N)个线程来对M个数字的数组进行排序，每个线程从位置(N*i)%m开始对数组进行排序。有人能帮我吗？
回答 3
Stack Overflow用户
发布于 2010-10-29 03:47:07
您需要做的是使用像quick sort这样的divide and conquer排序方法。
您需要做的是对数组进行分区，然后将数组的两部分传递给另一个线程进行处理。
假设你有号码：
11 43 24 56 12 65 90 12 53 23在一个线程中，您将对数字进行分区：
12 24 11 23 12 | 65 90 53 56 43然后，您可以在不同线程中对数组的每一半执行快速排序。
请允许我提供一些代码：
public void multiThreadSort(int threads, int[] arr, int start, int stop) {
if (threads > 1) {
int midpoint = partition(arr, start, stop);
new Thread(){public void run() {
multiThreadSort(threads - 1, arr, start, midpoint);
}}.start();
new Thread(){public void run() {
multiThreadSort(threads - 1, arr, midpoint, stop);
}}.start();
}
else
Arrays.sort(arr, start, stop);
}
public int partition(int[] arr, int start, int stop);然后这样叫它：
multiThreadSort(N, arr, 0, arr.length());Stack Overflow用户
发布于 2010-10-29 03:54:22
您可以让每个线程使用Arrays.sort(arr, fromIndex, toIndex)对数组中自己的部分进行排序，在所有线程完成之后，只需使用合并排序来合并不同的结果。(即使这一步也可以通过一次合并多个部分来并行化。)
Stack Overflow用户
发布于 2010-10-29 03:58:41
另一个问题是你为什么要这样做？线程的创建和销毁相当繁重，排序(如果您可以将设置保存在内存中)相当快。只有当您由于其他原因在线程池中预先存在线程时，如果排序M的时间比创建(可能是销毁)线程的时间长得多，或者这是一个学习线程操作的学术练习(在这种情况下，您不应该在这里询问)，这样做才有意义。如果对M进行排序的时间大于创建线程的时间，您可能会将部分数组放在虚拟内存中，并且磁盘分页效果将主导您的性能。
对于某些算法，线程是非常有用的，甚至是必不可少的。排序不是一个好的应用程序。除了，如上所述，作为一种学习练习，以获得编写软件的经验，您的线程可以很好地协同工作。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4046600
复制相关文章
相似问题
腾讯云开发者
