multithreading排序算法

我必须在Java中为我的算法类实现multithreadingMerge Sort和Quick排序，并将它们与我的单线程版本进行比较。 但是，我以前从来没有multithreading。

代码我能够multithreading还是我必须重新开始？

这是我的单线程算法Merge Sort的代码。 sort（）方法是我必须实现的策略模式的一部分。

@Override public int[] sort(int[] list) { int array_size = list.length; list = msort(list, 0, array_size-1); return list; } int[] msort(int numbers[], int left, int right) { int mid; if (left<right) { mid = (right + left) / 2; msort(numbers, left, mid); msort(numbers, mid+1, right); merge(numbers, left, mid, mid+1, right); } return numbers; } void merge(int numbers[], int startA, int endA, int startB, int endB) { int finalStart = startA; int finalEnd = endB; int indexC = 0; int[] listC = new int[numbers.length]; while(startA <= endA && startB <= endB){ if(numbers[startA] < numbers[startB]){ listC[indexC] = numbers[startA]; startA = startA+1; } else{ listC[indexC] = numbers[startB]; startB = startB +1; } indexC++; } if(startA <= endA){ for(int i = startA; i < endA; i++){ listC[indexC]= numbers[i]; indexC++; } } indexC = 0; for(int i = finalStart; i <= finalEnd; i++){ numbers[i]=listC[indexC]; indexC++; } } 

这是我的快速排序

  @Override public int[] sort(int[] list) { int[] array = quickSort(list, 0, list.length-1); return array; } int partition(int arr[], int left, int right) { int i = left, j = right; int tmp; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr[i]  pivot) j--; if (i <= j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } }; return i; } int[] quickSort(int arr[], int left, int right) { int index = partition(arr, left, right); if (left < index - 1) quickSort(arr, left, index - 1); if (index < right) quickSort(arr, index, right); return arr; } 

干杯!

Answer 1

简短的回答 – 是的，这些算法可以转换为multithreading而无需从头开始（据我所见）。

使这些“易于”并行化的关键要素是：

• 每个实现中有两个递归调用
• 这两个递归调用对不同的数据进行操作 – 它们不应相互冲突（例如，即使在同一个数组中工作，它们也在不同的索引上运行）
• 进行这些递归调用的方法在完成之前无法继续
• 这两个调用的顺序无关紧要

希望你已经回答了一些问题。

---

一些更多的建议，不确定这将是多么有用：

• 如果将两个递归调用放入一个新线程，那么当前线程将在等待它们完成时处于空闲状态
• 当剩下要处理的元素数量很少时，线程的开销可能高于增益。
• 您可能希望限制通常用于此任务的线程数 – 您可能希望使用某种forms的线程池或工作队列，并使用固定数量的线程。

Answer 2

在这种情况下的一个主要建议（当我在你的鞋子里，我已经看到许多其他人这样做时，我犯了一个错误）是不要让线程的数量不受限制。 请记住，如果你为每个递归分支启动一个线程，主线程将产生一个子线程（假设一个递归调用在main本身完成），子线程将产生一个额外的线程，依此类推，直到你将阻塞系统，如果你的数据集很大。

一个更明确的选择是每次递归调用启动一个线程，这样每个线程产生两个子线程然后连接它们。

无论哪种方式，请确保对生成线程的递归深度设置限制（假设等于CPU核心数），如果超出限制，则在其余级别上按顺序调用sort方法。