Tag: quicksort mergesort

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, […]

Quicksort比Mergesort慢？

我昨天正在努力实现一个快速排序，然后我运行它，期望比Mergesort更快的运行时间（我也已实现）。 我运行了两个，虽然快速排序对于较小的数据集<100个元素更快（并且我确实validation了它的工作原理），但mergesort很快就成为了更快的算法。 有人告诉我，快速排序几乎总是比mergesort“更快”，我知道在这个主题上有一些争论，但我至少预计它会比这更接近。 对于数据集> 10000个元素，mergesort的速度提高了4倍多。 这是预期的，还是我的快速排序代码中有错误？ 归并排序： public static void mergeSort(int[ ] e) { if (e.length <= 1) return; int[] first = new int[e.length/2]; int[] second = new int[e.length – first.length]; System.arraycopy(e, 0, first, 0, first.length); System.arraycopy(e, first.length, second, 0, second.length); mergeSort(first); mergeSort(second); System.arraycopy(merge(first, second), 0, e, 0, e.length); } private static int[] merge(int[] first, […]

Java：如何对自定义类型ArrayList进行排序

我有一个自定义类型Position(x,y,z) ，现在我创建一个ArrayList ，我想按z的值排序这个数组，从小到大，我怎么能用Collections.sort做到这一点还是有其他有效的排序方法？ 当我尝试使用时 public class PositionComparator implements Comparator { @Override public int compare(Position o1, Position o2) { // TODO Auto-generated method stub return o1.height().compareTo(o2.height()); } } 得到一个错误 Cannot invoke compareTo(double) on the primitive type double