首页 / 算法 / java – 多线程排序算法
java – 多线程排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java – 多线程排序算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2301字,纯文字阅读大概需要4分钟。
内容图文
![java – 多线程排序算法](/upload/InfoBanner/zyjiaocheng/748/4cb3d00a10a9416bb6c0ad326dcb5a5e.jpg)
我必须在Java中为我的算法类实现多线程Merge Sort和Quick排序,并将它们与我的单线程版本进行比较.但是,我以前从来没有多线程.
代码我能够多线程还是我必须重新开始?
这是我的单线程算法的代码
合并排序. 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)
i++;
while (arr[j] > 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;
}
干杯!
解决方法:
简短的回答 – 是的,这些算法可以转换为多线程而无需从头开始(据我所见).
使这些“易于”并行化的关键因素是:
>每个实现中都有两个递归调用
>这两个递归调用对不同的数据进行操作 – 它们不应相互冲突(例如,即使在同一个数组中工作,它们也在不同的索引上运行)
>完成这些递归调用的方法无法继续进行
>这两个电话的订单无关紧要
希望能回答你的一些问题.
一些更多的建议,不确定这将是多么有用:
>如果将两个递归调用放入一个新线程,那么当前线程将在等待它们完成时处于空闲状态
>当剩下要处理的元素数量很少时,线程的开销可能高于增益.
>您可能希望限制通常用于此任务的线程数 – 您可能希望使用某种形式的线程池或工作队列,并使用固定数量的线程.
内容总结
以上是互联网集市为您收集整理的java – 多线程排序算法全部内容,希望文章能够帮你解决java – 多线程排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。