Tag: mergesort

Java递归和合并排序: 我正在尝试用Java编写一个简单的合并排序程序，我在Eclipse中看到了很多红色。我还是个初学者，并没有看到什么是错的。谢谢。 -Kyle public class merge{ public static int[] mergeSub(int[] array, int left, int right){ if(left<right) { int mid = (left+right)/2; int[] a = mergeSub(array, left, mid); int [] b = mergeSub(array, mid+1, right); return merge(a, b); } int[] arr=new int[1]; arr[0]=arr[left]; return arr; } static int[] merge(int[] left, int[] right){ int index =0; […]

multithreading合并排序算法: 我有一个类在genericsList上进行一些递归合并排序，只要该元素实现Comparable。我正在尝试使代码multithreading以提高性能，为此，我有一个静态变量maxThreads ，它保持我创建的线程数不爆炸，我有一个静态变量currentThreads跟踪我目前运行的线程数。我的currentThreads变量似乎存在竞争条件，但我无法找到解决方案来修复它。 import java.util.ArrayList; import java.util.List; public class ThreadedMergeSorter<E extends Comparable> implements, Runnable { private List list; private List left, right; private Thread t1, t2; private static final int maxThreads = 4; private static AtomicInteger currentThreads = new AtomicInteger(0); private ThreadedMergeSorter(List list) { this.list = list; } public ThreadedMergeSorter(){} /** * Sorts a […]

mergeSort实现，用于查找尝试从文件读取时无效的反转次数: 我试图做一个mergesort实现来查找反转次数。。该数组似乎返回了一个硬编码的小数字列表的正确结果，但是当我从文件中读取时返回的数字不正确。我猜它与字符串整数比较有关，但无法弄清楚究竟是什么问题，。任何见解都会有所帮助。这是（相关）代码 – public class ReadFile { public static void main(String args[]){ int count=0; int n[]; int i=0; try{ n=OpenFile(); int num[] = new int[n.length]; for (i=0;i<n.length;i++){ num[i]=n[i]; // System.out.println( "Num"+num[i]); } count=countInversions(num); } catch(IOException e){ e.printStackTrace(); } System.out.println(" The number of inversions"+count); } public static int [] OpenFile()throws IOException{ FileReader fr=new […]

Mergesort交换和比较: 我正在研究一个分析项目，我正在观察在Java中实现时不同算法的行为方式。我得到了一些在线实现Mergesort算法的代码，现在我需要在10,000个随机生成的整数（1到100,000之间）的数组上运行此代码，并记录进行了多少次交换和比较。我不确定代码中的哪一点增加了计算Swaps和Comparisons的变量。期望值是多少？因为Mergesort的最佳，最差和平均情况都是nlog（n）这是否意味着我应该期望10,000 *（10,000的基数2）约为138,000，换算和比较的总和？这是代码，我猜测交换仅在原始数组被更改时发生，比较我不太确定： void MergeSort(int low, int high) // a[low : high] is a global array to be sorted. // Small(P) is true if there is only one element to // sort. In this case the list is already sorted. { if (low < high) { // If there are more […]

如何合并使用O（nlogn）时间和O（1）空间复杂度对链接列表进行排序: （免责声明：上学）据我所知，递归拆分链表，然后将其发送到另一个要合并的函数是O（nlogn）时间和O（n）空间。在O（nlogn）时间和O（1）空间复杂度的链表上是否可以进行合并？你会怎么做呢？任何帮助都表示赞赏 PS：为了确保传统的mergesort是空间复杂度0（n），这是0（n）的一个例子，对吧？如何改变O（1）空间？ void sortTrack() { Node merge = this.head; this.head = Node (merge); } public Node mergeSort(Node head){ if ((head == null)||(head.next == null)){ return head; } Node left = head; Node right = head.next; while((right != null) && right.next != null){ head = head.next; right = right.next.next; } right […]

合并排序Java: 我正在尝试创建一个合并排序方法，但它继续给出错误的排序。我在哪里进行更改以使其实际排序数组？代码的哪一部分必须不同？感谢您的时间。 public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) { int elements = (rHigh – lHigh +1) ; int[] temp = new int[elements]; int num = left; while ((left <= lHigh) && (right <= rHigh)){ if (a[left] <= array[right]) { temp[num] = array[left]; left++; } else { […]

为什么合并排序不稳定？: 下面的实现是稳定的，因为它使用<=而不是<在标记为XXX的行。这也使它更有效率。有没有理由在这一行使用<而不是<= ？ /** class for In place MergeSort **/ class MergeSortAlgorithm extends SortAlgorithm { void sort(int a[], int lo0, int hi0) throws Exception { int lo = lo0; int hi = hi0; pause(lo, hi); if (lo >= hi) { return; } int mid = (lo + hi) / 2; /* * Partition the […]

动态增加java堆空间: 我编写了一个java程序，用于测试具有不同处理器数量的不同机器上的几个multithreading算法的速度。在某些机器上，merge sort *失败，因为它需要一个相当大的堆空间来处理非常大的数组。在运行程序之前，我可以自己轻松地更改java堆空间，但我觉得更强大，更简单的方法是从程序本身执行此任务。有没有办法在java程序的过程中从虚拟机请求/实现更多的堆空间？注意：我确实理解我可以用“java -Xmx1g Program”这样的脚本执行程序; 我对这个问题的好奇心部分是学术性的。 *我的实现不会在线合并。它需要O（n）额外的内存。

为什么Java 6 Arrays＃sort（Object ）从mergesort更改为insertionsort用于小数组？: 如果数组长度小于某个阈值，则Arrays.java Java 6的mergesort实现使用Arrays.java -sort。此值被硬编码为7.由于算法是递归的，因此对于大型数组，这最终会发生多次。规范的合并排序算法不会这样做，只需使用merge-sort，直到列表中只有1个元素。这是优化吗？如果是这样，它应该如何帮助？为什么7 ？插入排序（甚至<=7件事）会大大增加对大型数组进行排序所需的比较次数 – 因此会增加compareTo()调用速度慢的排序成本。（x轴是size of array ，y轴是# of comparisons ，对于不同的INSERTIONSORT_THRESHOLD值）