用Java标准LinkedList搜索Mergesort算法
用Java标准LinkedList搜索Mergesort算法
提问于 2019-05-18 14:59:29
我想使用Mergesort算法在Java中对LinkedList进行排序。
我在互联网上研究了一种解决方案，但我找到的算法要么对数组进行排序，要么对自声明的LinkedList进行排序。正如我前面提到的，我需要一个对标准的java LinkedList (java.util.LinkedList)进行排序的算法。
除了我的研究之外，我试图自己实现一个，但我没有能力这样做。我能够创建‘划分’部分，但我无法编程‘征服’(合并按排序顺序)部分。
这是我的密码：
private void mergeSort(LinkedList<Integer> list) {
if (list.size() < 2){
return;
}
int middleindex = list.size()/2;
LinkedList<Integer> [] listArr = split(list, middleindex);
LinkedList<Integer> leftList = listArr[0];
mergeSort(leftList);
LinkedList<Integer> rightList = listArr[1];
mergeSort(rightList);
sortedMerge(rightList, leftList, list);
}
private void sortedMerge(LinkedList<E> right, LinkedList<E> left, LinkedList<E> list){
//sort and merge
}
@SuppressWarnings("unchecked") private static <T> LinkedList<T>[] split(LinkedList<T> list, int index) {
LinkedList<T> left = new LinkedList<>();
for (int i = 0; i < index; i++) {
T t = list.removeFirst();
left.addLast(t);
}
return new LinkedList[] {
left, list
};
}有人能帮我创建'sortedMerge()‘方法吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-05-21 18:17:41
Collections.sort()方法对LinkedList进行排序。它将LinkedList的内容复制到数组中，对数组进行排序，并将数组的内容复制回LinkedList。您可以实现与Collections.sort()方法相同的功能，并使用合并排序算法对数组进行排序。
下面我详细介绍了使用合并排序算法对Java标准LinkedList排序的步骤和正确的代码。
步骤：
- 创建一个LinkedList 'orginialList‘
- 将“originalList”转换为整数数组“arr”
- 将'arr‘转换为int数组'intArray’
- 使用合并排序算法对“intArray”排序
- 将排序的'intArray‘转换回整数数组'arr’(使用for循环来更改‘arr’中的元素)
- 创建一个LinkedList 'newList‘
- 在“newList”中添加“arr”元素(使用Arrays.asList(arr))
public static class CollectionsSort {
public static void main(String[] args) {
LinkedList<Integer> originalList = new LinkedList<>();
originalList.add(3);
originalList.add(2);
originalList.add(1);
Integer[] arr = list.toArray(new Integer[list.size()]);
int[] intArray = new int[arr.length];
for (int i = 0; i < intArray.length; i++) {
intArray[i] = arr[i].intValue();
}
mergesort(intArray);
for (int i = 0; i < arr.length; i++) {
arr[i] = new Integer(intArray[i]);
}
LinkedList<Integer> newList = new LinkedList(Arrays.asList(arr));
Iterator it = newList.iterator();
while(it.hasNext()) {
System.out.print((int)(it.next()) + " ");
}
}
public static int[] mergesort(int[] arr) {
int low = 0;
int high = arr.length-1;
mergesort(arr, low, high);
return arr;
}
public static void mergesort(int[] arr, int low, int high) {
if (low == high) {
return;
} else {
int middle = low + (high-low)/2;
mergesort(arr, low, middle);
mergesort(arr, middle+1, high);
merge(arr, low, middle, high);
}
}
public static void merge(int[] arr, int low, int mid, int high) {
int[] left = new int[mid-low+2];
for (int i = low; i <= mid; i++) {
left[i-low] = arr[i];
}
left[mid-low+1] = Integer.MAX_VALUE;
int[] right = new int[high-mid+1];
for(int i = mid+1; i <= high; i++) {
right[i-mid-1] = arr[i];
}
right[high-mid] = Integer.MAX_VALUE;
int i = 0, j = 0;
for(int k = low; k <= high; k++) {
if(left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
}
}
}Stack Overflow用户
发布于 2019-05-30 19:52:50
示例代码(包括main()中的测试代码)用于Java LinkedList的自下而上的合并排序，它使用一个小的列表数组(32) (与自顶向下将列表拆分和推到堆栈上的方法相反)。由于Java没有与std：：list：：LinkedList ()等效的C++，它将在列表中移动节点(或从一个列表移动到另一个列表)，因此创建和删除节点和列表，这会增加大量开销。
package llsort;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Random;
public class llsort {
public static LinkedList<Integer> Merge(LinkedList<Integer> ll0, LinkedList<Integer> ll1){
LinkedList<Integer> ll = new LinkedList<>();
if(ll0.isEmpty()) // empty list check
return (ll1);
if(ll1.isEmpty())
return (ll0);
ListIterator <Integer> ll0i = ll0.listIterator(0);
ListIterator <Integer> ll1i = ll1.listIterator(0);
Integer e0;
Integer e1;
e0 = ll0i.next(); // merge lists
e1 = ll1i.next();
while(true){
if(e0 <= e1){
ll.add(e0);
if(ll0i.hasNext()){
e0 = ll0i.next();
continue;
}
ll.add(e1);
while(ll1i.hasNext())
ll.add(ll1i.next());
break;
}else{
ll.add(e1);
if(ll1i.hasNext()){
e1 = ll1i.next();
continue;
}
ll.add(e0);
while(ll0i.hasNext())
ll.add(ll0i.next());
break;
}
}
return ll;
}
public static LinkedList<Integer> MergeSort(LinkedList<Integer> src){
final int NUMLIST = 32;
LinkedList<Integer>[] all = new LinkedList[NUMLIST];
LinkedList<Integer> ll;
int i;
// merge nodes into array
ll = new LinkedList();
while(!src.isEmpty()){
ll.add(src.peek());
src.remove();
for(i = 0; i < NUMLIST && all[i]!= null; i++){
ll = Merge(ll, all[i]);
all[i] = null;
}
if(i == NUMLIST)
i--;
all[i] = ll;
ll = new LinkedList();
}
// merge array into list
ll = new LinkedList();
for(i = 0; i < NUMLIST; i++)
if(all[i] != null)
ll = Merge(ll, all[i]);
return ll;
}
public static void main(String[] args) {
final int NUMELEM = 2*1024*1024;
LinkedList<Integer> ll = new LinkedList<>();
Random r = new Random();
for(int i = 0; i < NUMELEM; i++)
ll.addLast(r.nextInt());
long bgn, end;
bgn = System.currentTimeMillis();
ll = MergeSort(ll);
end = System.currentTimeMillis();
System.out.println("milliseconds " + (end-bgn));
// check sort
while(true){
int i = ll.peek();
ll.remove();
if(ll.isEmpty())
break;
if(i > ll.peek()){
System.out.println("error");
break;
}
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56200120
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号