Tag: 快速排序

使用随机数据块进行简单的快速排序实现: 我正在审查算法的东西，并坚持在Java中的简单的快速排序算法实现 import java.util.Arrays; import java.util.Random; public class QuickSort { int arr[]; boolean randomPick; Random rand = null; public QuickSort(int[] inputArray) { arr = inputArray; randomPick = false; } public QuickSort(int[] inputArray, boolean random) { arr = inputArray; if (random) { randomPick = true; rand = new Random(System.currentTimeMillis()); } else { randomPick = false; } } […]

并行化快速排序使其变慢: 我正在快速搜索大量数据，为了获得乐趣，我尝试将其并行化以加快排序速度。但是，在它的当前forms中，由于同步阻塞点，multithreading版本比单线程版本慢。每次我生成一个线程时，我都会对一个int进行锁定并递增它，并且每次线程完成时我都会再次获得锁定和减少，此外还要检查是否还有任何线程仍在运行（int> 0）。如果没有，我唤醒我的主线程并使用已排序的数据。我相信有更好的方法可以做到这一点。不知道它是什么。非常感谢帮助。编辑：我想我没有提供足够的信息。这是octo-core Opteron上的Java代码。我无法切换语言。我正在排序的数量适合内存，并且在调用quicksort时它已经存在于内存中，因此没有理由将其写入磁盘只是将其读回内存。通过“获取锁定”我的意思是在整数上有一个同步块。

在字符串数组上使用quicksort: 我是一名编程学生，而不是发布整个作业，我只是要求帮助解决我已经尝试了几个小时现在才能理解的内容。我的任务是使用quicksort方法对字符串数组进行排序。我作为这个问题的一部分负责的其他所有事情都很好但是当我通过打印字符串数组测试排序方法时，它完全混乱，没有任何看似押韵或理由。请帮我查明代码中的错误，或者我忽略的几个明显的错误。提供的字符串数组是65个名称的列表： http ： //pastebin.com/jRrgeV1E ，方法的代码如下： private static void quickSort(String[] a, int start, int end) { // index for the “left-to-right scan” int i = start; // index for the “right-to-left scan” int j = end; // only examine arrays of 2 or more elements. if (j – i >= 1) { […]

Quicksort-枢轴选择策略如何影响quicksort的整体Big-oh行为？: 我提出了几个策略，但我不完全确定它们如何影响整体行为。我知道平均情况是O（NlogN），所以我认为这将是某个地方的答案。如果我只选择数组中的第一项作为快速排序的枢轴，我想把NlogN + 1放入，但我不知道这是正确还是可接受？如果有人能够在这个主题上启发我会很棒。谢谢！可能的策略： a）数组是随机的：选择第一项，因为这是最具成本效益的选择。 b）数组主要是排序的：选择中间项，这样我们很可能会赞美每次拆分的二进制递归。 c）数组相对较大：选择数组中的第一个，中间和最后一个索引并比较它们，选择最小的索引以确保避免最坏的情况。 d）使用随机生成的索引执行’c’，以使选择更不确定。

在quicksort应用程序中这些交换代码行的目的是什么？: 我试图理解quicksort的实现或应用程序来找到第k个最小元素这是我想要了解的代码 public int quicksort(int a[], int start, int end, int k) { if(start k – 1){ return quicksort(a, start, pivot, k); } else { return quicksort(a, pivot + 1, end, k); } } else if(start == end) { return k==1?start:-1; } else { return -1; } } public int partition(int a[], int start, int end) […]

使用Java中的随机数据库快速排序: 我被指派用一个随机的枢轴点来实现快速排序（因为它被认为是最有效/最安全的方式），但我一直在奴役一个bogosort。任何人都可以指导我如何做到这一点？并且有人可以帮助我看看我的bogosort，看看我是否可以保存它？ public static void Quick(int[] target, int lo, int hi) { if(hi-lo==0){return;} Random numberGenerator = new Random(); int pivot = (numberGenerator.nextInt(hi-lo)+lo); int high; for(high=hi; high>pivot ; high–){ if(target[high]<target[pivot]){ //if highest was smaller than pivot, move far end if(high-pivot==1){ int temp=target[high]; target[high]=target[pivot]; target[pivot]=temp; } else{ int temp1 = target[pivot]; int temp2 = target[pivot+1]; target[pivot]=target[high]; […]

Java：通过multithreading并行化快速排序: 我正在尝试在Java中并行化算法。我从合并排序开始，并在这个问题上发布了我的尝试。我修改过的尝试是在下面的代码中，我现在尝试并行快速排序。我的multithreading实现或解决此问题的方法是否有任何新手错误？如果不是，我不应该期望在双核上的顺序算法和并行算法之间的速度增加超过32％（参见底部的时间）？这是multithreading算法： public class ThreadedQuick extends Thread { final int MAX_THREADS = Runtime.getRuntime().availableProcessors(); CountDownLatch doneSignal; static int num_threads = 1; int[] my_array; int start, end; public ThreadedQuick(CountDownLatch doneSignal, int[] array, int start, int end) { this.my_array = array; this.start = start; this.end = end; this.doneSignal = doneSignal; } public static void […]

使用Quicksort Java实现的Stackoverflow: 在java中实现quicksort时遇到一些问题。我运行这个程序时出现stackoverflow错误，我不确定为什么。如果有人能够指出错误，那就太好了。 si是起始指数。 ei是结束指数。 public static void qsort(int[] a, int si, int ei){ //base case if(ei=ei){} else{ int pivot = a[si]; int length = ei – si + 1; int i = si+1; int tmp; //partition array for(int j = si+1; j a[j]){ tmp = a[j]; a[j] = a[i]; a[i] = tmp; i++; } […]