-
2 votesanswersviews
了解合并排序和快速排序的运行时间
对于合并排序和快速排序,我试图想出最糟糕的情况 . 如果我是正确的,在排序所有内容时合并排序最差的情况O(nlogn) . 快速排序最糟糕的情况是当枢轴处于最不理想的位置,并且数组被排序,因此它变为O(n ^ 2) . 我想知道这是否正确,所以如果没有,请纠正我 . 我真正的问题是,如果快速排序的数据库位于数组的中间,那么数组必须是什么才能使它成为O(n ^ 2)? -
0 votesanswersviews
Quickselect vs Countingselect
基于计数排序,基于快速排序和计数选择进行快速选择 . 每个都能够在未排序/排序的列表/数组中找到第k个最小元素 . 但是,我希望编写一套指南来决定哪种算法最适合特定情况 . 我需要考虑情况,而不是实现哪种算法是更好的选择 . 为此,我需要帮助区分哪种算法在某些领域具有特定的优势等 . -
0 votesanswersviews
无法理解快速选择算法
我在理解快速选择算法时遇到问题 . 我知道它基于快速排序算法(我很熟悉)并且它为您提供了所需的结果,可能会使数组的一部分未排序 . 现在这里是我遇到困难的地方 . 问题是从数组中找到第二个最小的元素: int a[4] = {1,3,5,2} ; 现在假设我们正在随机选择枢轴然后根据this post我们有以下条件: k == pivot . 然后你已经找到了最小的第k个 . 这是因为分区... -
0 votesanswersviews
将顺序搜索与二进制搜索进行比较
假设我有一个未排序的实数数组,长度为 N . 我想找到最大的非正数 y ,然后在数组中找到小于 y 的第一个数字 x ,并且第一个数字 z 大于 y . 我想理论上将顺序搜索与二进制搜索非渐近地比较(即不仅仅是用大的Os)来找到这些值 . 陈述是否合理: 顺序搜索需要 0 排序比较, 3*N 搜索比较(三次连续搜索) . 二进制搜索需要 2*N*ln(N) ≈ 1.39*N... -
1 votesanswersviews
快速效率:扫描方向是否重要?
这是我的就地快速排序算法的实现,来自this视频的改编: def partition(arr, start, size): if (size < 2): return index = int(math.floor(random.random()*size)) L = start U = start+size-1 pivot = arr[... -
-1 votesanswersviews
快速排序的递归如何工作?
以下功能是快速排序的实现 . 这里我们将最后一个元素作为一个支点 . 我理解 partition 函数(其中枢轴到达其排序位置)但我无法理解递归函数 qs . 函数 qs 递归调用自身以通过 qs(a,start,pi-1) 解析左侧,并通过 qs(a,pi+1,end) 解析分区右侧 . 它解决了左边然后(左边的左边)然后(左边的左边)等,然后左边,左边......右边等等 . 或者通过解决左... -
0 votesanswersviews
快速排序算法中分区函数的修改
下面给出了我对作业的快速排序的实现 . 分区功能有望将列表分为三个部分 . 一个具有小于枢轴的元件,一个具有等于枢轴的元件,一个具有大于枢轴的元件 . 然后它应该返回包含等于pivot的元素的列表部分的开始和结束索引 . 我编写了以下代码,但每次执行相同的代码时,我都会得到不同的数组作为最终输出 . 请帮忙 . import random def random_sort(A,p,r): if ... -
2 votesanswersviews
具有相等元素的快速排序算法进程
我正在进行算法分配,这需要我用一个相等元素(1(a),1(b),1(c)等数组)显示快速排序算法的进展,其中枢轴是最后一个数组中的元素 . 算法的递归部分令我感到困惑 . 到目前为止,我有进展: 1(a) 1(b) 1(c) 1(d) [1(e)] 1(a) | 1(b) 1(c) 1(d) 1(e) 1(a) 1(b) | 1(c) 1(d) 1(e)... -
0 votesanswersviews
快速排序3方式 - 当元素大于数据透视时,为什么循环索引不会递增?
我一直在寻找与3 way quicksort相关的许多问题,但找不到答案/解释(像这样和类似的 - Quicksort with 3-way partition) . 以下是Robert Sedgewick和Kevin Wayne的书籍“算法”中的3向快速排序代码 . private static void sort(Comparable[] a, int lo, int hi) { ... -
0 votesanswersviews
如何修改QuickSort以使枢轴处于正确位置
考虑如下的数组, int[] a = {100, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 16}; 考虑中间元素始终作为枢轴 . pivot = 10 标准快速排序算法如下所示 public void quickSort(int[] a, int low, int high) { if (a == null || a.length == 0... -
1 votesanswersviews
Hoare的quicksort是如何工作的,即使partition()之后的pivot的最终位置不是它在排序数组中的位置?
所有变量名都来自Quicksort's wikipedia page 's Lomuto'和Hoare的快速排序伪代码 . 如果 p 是 partition 函数返回的内容,则Hoare将其数组从 lo 分割为 p ,将 p+1 分割为 hi ,而Lomuto将其数组从 lo 分割为 p-1 ,将 p+1 分割为 hi . 我可能错了,但Quicksort的理念是...... 获取子阵列(p... -
0 votesanswersviews
快速排序算法无法正常工作?
我的快速排序算法没有返回正确的输出 . 我的输出只是右侧的枢轴元素,左侧的元素小于枢轴元素,右侧的元素大于枢轴元素 . import java.util.Timer; class QuickSort { public static void quicksort(int[] array, int left, int right) { if (left < rig... -
0 votesanswersviews
使用随机分区进行就地快速排序,仅将数组作为参数
当给出以下分区方法时,我需要在java中实现快速排序: private static int partition (int[] A, int low, int high) { int pivot, tmp, l, r; pivot = low + qsr.nextInt(high - low + 1); l = low; r = high-1; tmp = A[pivot]; A[pivot] =... -
1 votesanswersviews
按降序排列的 QuickSort 在重复的条目上无法正常工作
我在使用递归快速排序算法时遇到了一些问题。元素未按正确顺序排序。输入数据也是具有重复条目的字符串。我使用整数来区分升序(1)和降序(-1)排序。枢轴是中间元素。每当比较重复的条目时(compareTo(String s 都将返回 0),如果要比较的字符串的索引大于 other.I 的索引,则我将比较当前索引并返回负数,我不确定到底是什么错误。下面是代码 // Quick sort Algorith... -
316 votesanswersviews
为什么quicksort比mergesort更好?
我在接受采访时被问到这个问题 . 他们都是O(nlogn),但大多数人使用Quicksort而不是Mergesort . 这是为什么? -
2 votesanswersviews
算法:分而治之(快速排序的应用?!)
关于如何处理下面的问题的任何帮助将不胜感激 . 我也对这个问题发表了一些看法 . 您是一个招收n名学生的 class 的助教 . 你有他们的最终分数(未分类),你必须为他们分配一个G可用等级(A,B,C等) . 约束是(假设n是G的倍数):完全(n / G)学生得到每个年级(例如,如果n = 30,G = {A,B,C},那么正好10个学生得到A,得分为10,得分为10)得分较低的学生得分不高于... -
2 votesanswersviews
选择排序,插入排序和快速排序的方案
如果有人能对我的逻辑给出一些意见,我会非常感激 . 对于所有键相同,选择排序或插入排序的数组,哪种方法运行得更快? 我认为这与数组已经排序时类似,因此插入排序将是线性的,选择排序是二次的 . 对于数组,哪种方法以相反的顺序,选择排序或插入排序运行得更快? 我认为它们的运行方式类似,因为每个位置的值都必须改变 . 插入排序的最坏情况是逆序,因此这意味着它是二次的,然后选择排序也已经是二次的 ... -
23 votesanswersviews
随机化三分之一的快速排序是否明显优于随机快速排序?
我刚刚回答了一个关于在快速实施中选择分区的不同方法的问题,并提出了一个我真的不知道如何回答的问题 . 这有点数学,这可能是错误的网站,所以如果这需要移动请告诉我,我很乐意将其迁移到其他地方 . 它's well-known that a quicksort implementation that picks its pivots uniformly at random will end up ru... -
-2 votesanswersviews
快速排序中的非静态字段,方法或属性需要对象引用[重复]
这个问题在这里已有答案: CS0120: An object reference is required for the nonstatic field, method, or property 'foo' 6个答案 错误: 非静态字段,方法或属性'Program.Quicksort(int [],int,int)'In Quicksort需要对象引用 . 非静态字段,方法或属性'Pr... -
37 votesanswersviews
为什么quicksort比radix-sort更受欢迎?
为什么quicksort(或introsort)或任何基于比较的排序算法比radix-sort更常见?特别是对于数字排序 . 基数排序不是基于比较的,因此可能比O(nlogn)更快 . 实际上,它是O(kn),其中k是用于表示每个项目的位数 . 并且内存开销并不重要,因为您可以选择要使用的桶数,并且所需的内存可能小于mergesort的要求 . 它与缓存有关吗?或者可能访问数组中的随机字节整数? -
-3 votesanswersviews
使用c#中的unit4.dll库进行数据透视排序[暂停]
嗨我需要帮助在c#中用节点编写一个pivot(quicksort)函数 . 节点库名为unit4.dll,需要将其从https://docs.google.com/file/d/0B6qdiDO9VfXsMmp1ZnF1SHp2T3c/edit下载 -
-1 votesanswersviews
在数据库查询引擎中快速选择Min,Max,Ordered by
我正在和大学的 C++ Main Memory Database Query Engine 项目合作 . 这是我的查询引擎的快速工作流程,它应该能够: 加载我们RAM中的所有数据, 解析终端的SQL查询(不支持所有语法), 为此查询生成 C++ 代码并运行代码, 将结果传递为 std::cout . 现在的任务是使用 Min , Max , ordered by 关键字... -
0 votesanswersviews
为什么快速排序的分区方法在低等于高时不保证分区
当下面的片段中的低等于高时,为什么下面的快速排序分区方法不能保证低/高左侧的元素小于枢轴,而低/高的右侧的元素大于枢轴 . int middle = low + (high - low) / 2; int pivot = a[middle]; while (low < high) { while (a[low] < pivot) ...