3回答
堆排序是“分而治之”排序还是优先级队列排序？
另外，冒泡排序适合哪一类排序(除了可怕之外)。
我读到过堆排序通常被认为是一种“分而治之”的排序，但它也可以是优先级队列排序。严格来说是其中之一还是另一个？还是两者兼而有之呢？我找不到任何关于冒泡排序可以被考虑的东西。
浏览 2提问于2013-03-19得票数 3
回答已采纳
3回答
堆排序的应用
、、、
Heapsort是一种时间复杂度为O(nlogn)的排序算法，它使用O(1)空间复杂度进行排序。然而，我知道，因为它是不稳定的，它找不到多少应用程序(f.e。(与其他排序算法相比)。
我知道它是用来安排时间的。
堆排序的一些实际应用是什么？
编辑:正如@AProgrammer所指出的，快速排序也不稳定。
浏览 0提问于2013-04-08得票数 4
因此，当我在处理编程竞赛(ACM ICPC等)中的一些实践问题时，人们经常可以采用O(N^2)解决方案，甚至更糟，并使用堆(C++中的priority_queue)或use来降低复杂性。(作为某种优化，在注意到模式中的“某些东西”之后)
例如，在“滑动窗口最大值”问题中，这几乎是：
For each window of size K in an array of size N, compute the maximum.
这里有一个简单的O(NK)算法，一个相当简单的O(nlogn)解决方案(甚至我都可以看到，使用一个堆)和一个O(N)解决方案，使用一个双端队列。
这些原则似乎是基于“丢弃”无用
浏览 1提问于2012-10-18得票数 2
回答已采纳
我正在学习Kruskal的算法，我遇到了几种不同的实现，我想知道它们之间的权衡可能是什么。两种实现方式如下：
实现1-将图中的所有边放入优先级队列PQ -从PQ中移除最小边e-如果e连接2个先前未连接的图组件(使用Union Find数据结构测试)，则将其添加到MST -重复，直到MST中的边数等于图中顶点的总数-1
实现二-对图中的所有边执行合并排序或快速排序-从排序的边数组中删除最小的边，然后执行与上述算法相同的操作
因此，唯一真正的区别在于是使用优先级队列还是在O(eloge)时间内执行预先排序。
这里的权衡是什么？这两种实现似乎对me - O(ElogV)都有相同的运行时。我之所以说l
浏览 0提问于2015-12-15得票数 0
我有一个二维的p_q数组，我想对这个数组按m_n的二维数组进行排序，其中p>m和p=km，q>n和q=kn，以及k是整数。例如，我有一个16*16的数组，我把它划分为4*4的2d数组，现在我想独立地对这4*4数组进行排序。在不需要额外内存的情况下，我可以使用哪种算法在place.means中对这些数据进行排序。
浏览 9提问于2009-08-15得票数 0
1回答
合并排序和堆排序
、、、
假设您希望通过首先将Heap排序应用于多个连续的子数组来改进合并排序。给定数组A，您的算法将A细分为子数组A1，A2···Ak，其中k是2的幂，并单独对每个子数组Ai应用堆排序。该算法继续对连续子数组进行合并，直到对数组进行排序。例如，如果k= 4，则首先应用堆排序对每个Ai进行排序，然后将A1与A2合并，A3与A4合并，然后应用合并函数一次获得排序数组。(a)当k=2时，所提出的算法是否改善了合并排序的渐近运行时间？那么k= log n(或最接近log n的2的幂)如何？证明是正当的。(b)建议的算法是否稳定？它在原地吗？证明你的答案。
所以我有个问题要解决，我在想，对于k=2来说，阈值太低
浏览 1提问于2022-02-09得票数 0
2回答
为什么在堆排序中使用平面列表？
、、、、
在heapsort中，数据存储在一个叫做“堆”的东西中。几乎我看到的所有实现都使用平面列表作为数据结构。
有人能给我解释一下为什么吗？
为什么不使用嵌套数组或二叉树的实例？明示不比内隐好吗？
是因为执行困难，比如遍历结构，还是其他原因？
浏览 0提问于2012-03-30得票数 0
回答已采纳
堆是适用以下条件的列表：
l[i] <= l[2*i] && l[i] <= [2*i+1]
对于0 <= i < len(list)
我在找就地排序。
浏览 1提问于2008-09-22得票数 2
回答已采纳
在CLRS书中，通过自顶向下的heapify构建堆具有O(n)的复杂性。堆也可以通过反复调用插入来构建，在最坏的情况下，插入的复杂性为nlg(n)。
我的问题是:为什么后一种方法的性能较差？
我问这个问题是因为我觉得数学背后有一些简单的见解。例如,
快速排序、合并排序和堆排序都是基于减少不必要的比较，但方法不同。快速排序:平衡分区，不需要比较左子集和右子集。合并排序:简单地比较两个子数组中的两个最小元素。堆排序:如果A的值大于B，则A的值比B的后代大，不需要与他们进行比较。
浏览 5提问于2014-01-29得票数 4
回答已采纳
当我在hackerranker的网站上做一些代码时，有一个问题告诉我，你必须使用堆排序并输出控制台给出的最小数量的ArrayList，但你不应该破坏树或堆的结构。
我认为这很简单，但我不知道如何解决它？所以请帮帮我。
浏览 0提问于2016-10-11得票数 0
2回答
我读到了Java编程中的堆。在我的教科书中，我发现了堆的定义:堆是一个完整的二叉树，具有以下属性: 1)根中的值是树中最小的项；2)每个子树都是堆
但是当我看关于堆的视频时，我发现堆的定义完全不同:在堆中，父键是更大的，然后是子键。
现在，我感到困惑，因为这两个定义不符合彼此。哪个定义是正确的？
谢谢!
浏览 6提问于2015-12-15得票数 0
回答已采纳
2回答
我正在复习。我想知道为什么它是在二叉树中实现的？它还能用别的树吗？比如三子节点树？还是四个？随着子计数的增加，虽然需要更多的比较来执行删除操作。树的高度可以降低更多的。我认为与二叉树实现相比，时间成本应该会显著降低的。
浏览 4提问于2010-10-10得票数 3
回答已采纳
虽然我知道这似乎是显而易见的，但我会解释我的困惑。我一直认为快速排序的最坏情况时间复杂度是O(n^2)。[Arrays.sort(int[])]()从Java 7到Java 13的文档说:该算法在上提供O(n log(n))性能--许多数据集导致其他快速数据集退化为二次性能，并且通常比传统的(单轴)快速排序实现更快。
这里的关键字是“多”，所以我假设这里的O(n log(n))指的是平均情况，而且仍然存在导致O(n^2)最坏情况的数据集。
但是在Java14和更高版本中，[Arrays.sort(int[])]()的文档说:该算法在所有数据集上提供O(n (N))性能。
那么，对于现在改进的快
浏览 6提问于2022-03-16得票数 2
回答已采纳
4回答
我理解快速排序和合并排序都需要为所构造的临时子数组提供O(n)辅助空间，而就地快速排序则需要递归堆栈帧的O(log n)辅助空间。但是对于堆排序，它似乎也存在构建临时堆的O(n)辅助空间的最坏情况，即使节点只是指向实际元素的指针。
我偶然发现了一个：
只需要O(1)额外的空间，因为堆构建在要排序的数组中。
但我认为这意味着原来的数组必须作为某种树来实现吗？如果原始数组只是一个向量，那么堆的内存似乎仍然需要分配。
浏览 4提问于2014-03-06得票数 36
回答已采纳
5回答
我不明白为什么堆排序被认为是一个内部排序算法。
我的意思是使用要排序的数组元素填充的额外数据结构，即堆，用于帮助提取最小值和排序过程。
所以我可能误解了这里的定义吗？
但是插入排序--例如，它显然是内部算法，即元素不需要额外的内存。
那为什么要把它放在原地呢？
浏览 0提问于2011-10-29得票数 15
回答已采纳
1回答
因此，我试图找出一些算法，这些算法以最类似于基于PQ的排序的方式进行，用于以下结构。
1堆
3堆
n-1堆
BST
平衡BST
例如堆排序和d堆。Heapsort使用2堆作为中间表示来对内容进行排序.对于堆排序，PQ是一个2堆，即使任何PQ都能工作。
浏览 0提问于2018-04-29得票数 0
我不知道这个算法是堆排序还是快速排序.
假设我有一个没有源代码的算法--它是不稳定的，在大型数据集上性能很好，对于有序和无序的集合，运行时间类似。
如果没有更多的信息，是否可以判断这个算法是堆排序还是快速排序？
浏览 5提问于2016-06-21得票数 2
回答已采纳
我已经搜索了很长一段时间了，但是我找不到visual c++对std::sort函数使用的算法，我知道GNU C++库使用Intro排序，但是似乎没有任何消息来源说明微软的可视c++使用哪一个！
浏览 9提问于2014-04-05得票数 5
回答已采纳
1回答
在构建排序算法对数组进行排序时，数组中有多少n个元素的排序速度比插入排序快？我知道快速排序适用于更多的元素，而插入排序适用于较小的元素。但是想知道Quick Sort的大小比插入排序好得多吗？
浏览 0提问于2018-11-13得票数 0
在“算法设计手册”中找到了这个问题，问题的解决方案是
Sort2()
initialize-tree(t)
While (not EOF)
read(x);
insert(x,t);
y = Minimum(t)
While (y != NULL) do
print(y → item)
y = Successor(y,t)
它被解释为“第二个问题允许我们在构造树之后使用最小操作和后继操作，我们可以从最小元素开始，然后重复查找后续元素，按照排序顺序遍历元素。”
我想我不是在跟踪Sort2()。如果y被初始化为最小节点，那么它不可能没有任何后续节点吗
浏览 0提问于2015-11-25得票数 1
回答已采纳
当我知道PQ在时间复杂度方面会更好的时候，我什么时候会选择Collections.sort()而不是PriorityQueue呢？
浏览 3提问于2014-03-23得票数 6
回答已采纳
我正试着解决这个密码问题。我实现了一个MaxHeap，并尝试弹出值以获得数组中最大的Kth元素，但我得到了超过时间限制的结果。
我的MaxHeap实现有什么问题吗?它是慢的，还是可以用更快的方法完成？
问题
class Solution {
private int capacity = 10;
private int size = 0;
int items [] = new int[capacity];
//parent = (i-1)/2
//left-child = 2i+1
//right-child = 2i
public int findKthLargest(int[] n
浏览 3提问于2021-12-02得票数 0
回答已采纳
1回答
每当我对最小堆进行堆排序时，就会得到反向排序数组。
是否有任何方法在不使用额外空间的情况下使用堆排序对最小堆进行排序？
浏览 6提问于2015-11-28得票数 0
2回答
分区函数给出快速排序它的局部性吗？如果有，怎么做？
我的意思是，与其他算法(例如合并排序或堆排序)相比，快速排序中有什么给出了引用的局部性？
我也读过
快速排序中的分区步骤通常具有很好的局部性，因为它访问前面和后面的连续数组元素。
我没明白吗？
浏览 5提问于2015-06-16得票数 10
回答已采纳
2回答
在这个中，我看到堆排序和合并排序对包含随机数的数组最有效。但是，如果我们将这些排序算法与基和内排序算法进行比较呢？
简而言之，哪种排序算法最适合对由随机数组成的数组进行排序？
谢谢
浏览 2提问于2018-09-23得票数 0
5回答
堆排序排序算法的最坏情况复杂度似乎为O(nlogn)，排序操作使用O(1)空间。
这似乎比大多数排序算法都要好。那么，为什么不总是使用堆排序作为排序算法(以及为什么人们使用像合并排序或快速排序这样的排序机制)？
此外，我还看到人们将“不稳定性”这一术语与堆排序一起使用。这意味着什么？
浏览 49提问于2011-11-29得票数 71
回答已采纳
我目前注册了一个为期一年的应用计算硕士课程，该课程旨在让没有计算背景的人参加一个软件开发和工程的速成课程，并为我们在技术行业的职业生涯做好准备。这门课程的其中一个课程，高级编程技术，涵盖了许多在C++中实现的排序算法，即快速排序、堆排序和Bubblesort。然而，一些本科生告诉我们，这些算法与行业无关，也没有得到广泛应用。这是真的吗?如果是真的，我应该看什么排序算法？
浏览 0提问于2011-04-01得票数 0
回答已采纳
3回答
我编写了以下方法，通过将最大值复制到另一个数组来对数组进行排序。我希望看到这种办法的替代办法。例如，一种交换主数组本身中的值的方法，从而消除了将值复制到次要数组的需要。
我不想使用预先编写的.net库方法，如Array.sort等，因为我的主要目标只是在编写算法方面进行实践。
另外，如果有人能告诉我以下代码的弱点和缺点，以及如何加以改进，我们将不胜感激。
谢谢
private static void sortArray(int[] array)
{
int[] sorted = new int[array.Length];
int curMax = 0;
i
浏览 5提问于2012-03-31得票数 2
回答已采纳
1回答
从快速排序开始，当递归深度超过基于要排序的元素数量的级别时，切换到堆排序。那是什么号码？是否有一个特定的范围或限制值？
浏览 2提问于2012-06-24得票数 7
回答已采纳
2回答
我正在为一场比赛做准备，无意中发现了这个问题:考虑一组n个元素，这些元素被排序，除了一个出现无序的元素。下列哪一项需要O(n)时间？
快速排序
堆排序
合并排序
气泡分类
我的理由如下：
我知道合并排序需要O(nlogn)，即使在最好的情况下也是如此，所以这不是答案。
快速排序也需要O(n^2)，因为数组几乎是排序的。
可以选择冒泡排序，但前提是我们稍微修改它，以检查是否在pass中进行了交换。
可以选择堆排序，就像我们创建排序数组的最小堆一样，它需要O(n)时间，因为只有一个人没有到位，所以他需要logn。
因此我认为它是堆类的。这个推理正确吗
浏览 1提问于2014-09-08得票数 0
回答已采纳
我们得到了一系列(x，y)坐标，我们需要找到离原点最近的点。当我们找到与原点距离相等的几个点，需要考虑其中一些点时，我们取其x坐标最小的点。如果两个x-坐标是相同的(这意味着2分相等)，我们取其中任何一个。
例如，给出了(1,1)，(-2, 3)，(2，3)和K=2
因此，答案是(1,1)和(-2，3)。
我的方法是-在原始点列表中的距离和位置之间生成一张地图。然后得到一系列的距离并对其进行排序。然后，我们取新排序数组中的每个距离，并扩展映射中的所有键(因此是原始数组中的位置)，如果它们超过1，并且还没有到达K，我们检查x坐标并将其添加到结果中。但我不能正确地实现这一点，我认为这不是最有效的方
浏览 9提问于2021-12-26得票数 1
回答已采纳
2回答
在过去的6个小时里，我一直在阅读有关构建堆排序的教程和学术资料。我终于在python中实现了对整数列表进行排序的原型。但是，我不能完全确定我的解决方案是否构成有效的堆排序。这是一个非常简单的解决方案，肯定可以改进，但我想知道它是否有效。令人困惑的是，每个人似乎都有自己的“首选”方式来实现这个算法。
在此之前，非常感谢您。
def heapsort(array):
array = heapify(array)
array = insert(array, 9999)
print(array)
def heapify(array):
end = len(array)
浏览 0提问于2015-06-01得票数 2
我在网上遇到了一个问题，询问从堆支持的Min优先级队列中获取最大值的平均时间复杂度。
我推断答案是O(n)，因为堆是由数组支持的，迭代数组一次以找到最大值需要进行n比较。
然而，答案是O(nlogn)。有谁能解释一下为什么会这样，为什么我的推理失败？
浏览 6提问于2017-12-11得票数 0
回答已采纳
我使用堆函数对数组进行排序。
import heapq
arr =[-74, 0, -4, 20, 7, 1, -4700, 74, 21, 71000, 87, 400, 9]
print ("The array: ", arr)
print("")
heapArray = arr
length = len(arr)
heapq.heapify(heapArray)
sortedArray = []
for each in (arr[:length]):
sortedArray.append(heapq.heappop(heapArray))
浏览 9提问于2022-06-08得票数 -1
问题是：
以最小的时间复杂度将k排序数组与n个元素合并到一个大小为nk的数组中。该算法应该是一个基于比较的算法。不应对输入作出任何假设。
因此，我知道有一种解决nklogk时间复杂性问题的算法，如这里所提到的：。
不过，我的问题是，我们能不能比nklogk少排序，这意味着，运行时是o(nklogk)。
于是我在网上搜索并找到了这样的答案：
它声称将一个大小为K的数组划分为单个数组，并将它们合并到一个数组中。但是这是不正确的，因为人们可以说他找到了一种解决sqrt(n)klogk问题的算法，即o(nklogk)但是n=1，所以我们在KlogK时间对数组进行排序，这与数组排序的下限并不矛盾
浏览 5提问于2022-05-22得票数 0
5回答
当一种特定的排序算法比其他算法更受欢迎时，有哪些用例-合并排序、QuickSort排序、堆排序、'intro排序‘等等？
根据它们的大小、数据结构类型、可用内存和缓存以及CPU性能，是否有推荐的使用指南？
浏览 3提问于2009-12-20得票数 179
1回答
书中写着：
堆排序最坏的运行时间是(nlgn)。这一点很明显，因为排序的下限为(nlgn)。
但是有人能帮我清楚地告诉我这个函数的下界等于Omega(nlgn)吗？
浏览 1提问于2014-03-20得票数 0
5回答
给出的问题陈述是：“您正在处理一个只有4 KB空闲内存的嵌入式设备( ATM)，并且您希望按照提取的金额(丢弃原始事务顺序)对2,000,000次具有-抽屉历史的事务进行排序。
对于这个问题陈述，我认为我们应该使用合并排序，这个排序算法有什么问题吗？
浏览 6提问于2015-12-20得票数 5
回答已采纳
1回答
我知道4.5的排序算法已经从4.0改变了，但我怀疑内省排序的实现有问题。在反向排序列表的情况下，行为似乎不正常，当某些人期望与“排序”情况(如4.0中的情况)相同的比较数时，这个数字非常大。
.net 4 x64
随机25514058，排序20525265，反向20525285
.net 4.5 x64
随机22112103，排序16935357，反向31148728！
我用来获得比较数(使用4.0和4.5编译)的代码是：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
浏览 3提问于2013-06-12得票数 1
1回答
堆算法时间复杂度
、、、、
有人能告诉我维基百科，中这个堆算法的时间复杂度到底是多少吗？
我搜索了几个网站，答案都很模糊，有些人说时间复杂度是O(N!)有些人说这是O(NlogN)。哪一个是正确的答案？为什么？
谢谢。
浏览 3提问于2017-03-18得票数 5
回答已采纳
6回答
对堆排序的直观理解？
、、、
在学校，我们目前正在学习Java中的排序算法，我的家庭作业是堆排序。我读了，我试着找出尽可能多的东西，但我似乎就是不能理解这个概念。
我并不是要你给我写一个Java程序，如果你能尽可能简单地向我解释堆排序是如何工作的话。
浏览 2提问于2012-01-20得票数 43
回答已采纳
2回答
所有这些排序算法都有O(n log n)的平均情况，所以我只想知道，如果我能够运行测试，但不知道运行的是哪种排序算法，我将如何区分这三种排序算法。
浏览 1提问于2013-05-16得票数 0
3回答
新的堆数据结构。
试图从列表中创建堆。
li = [5, 7, 9, 1, 3]
heapq.heapify(li)
在堆后，输出是
[1, 3, 9, 7, 5]
为什么要下这个命令？
我认为对于一个最小优先级堆，元素应该从min排序到max，即
heapq.heapify(li)应该与li.sort()相同
有人能帮我理解吗？
浏览 1提问于2018-05-31得票数 1
回答已采纳
1回答
平滑排序算法用在哪里？
、、、、
在我的大学学习算法的时候，我遇到了一个叫做Smoothsort的算法。这是一个很好的算法，因为它是一个自适应算法，时间复杂度可以从线性复杂度到线性复杂度变化，它也是一种就地算法。然而，关于该算法的资源非常稀缺，并且这些可用的资源非常难以理解。然而，我张贴这个问题的原因是为了了解用例，以及何时应该使用它，什么时候不应该使用它？
这就是我想知道的一切，非常感谢你回答或评论这个问题。
浏览 10提问于2020-09-13得票数 2
我们得到了一个整数数组：
45, 10, 56, 42, 95, 78.
我们必须找到差异最小的两个元素。我在线性时间复杂度中做到了这一点，但它只在排序的顺序上工作，这总共导致了二次复杂度的运行时间。我们有什么方法可以在对数或线性时间复杂度下做到这一点吗？
提前谢谢。
浏览 0提问于2015-08-02得票数 3
维基百科说，最糟糕的时间复杂性是O(n)。
然而，参考这个答案，，一些自选运行2lg(n)时间的partition_pivot的实现，这有一个最糟糕的时间复杂性O(nlg(n))。无论您使用堆排序的medians_of_medians算法，时间复杂度已经是O(nlg(n))。
如何实现最糟糕的O(n)自选？如果我们使用常量k而不是2lg(n)。我们可以说时间是O(n)吗？你能给我一些关于k(必须是常数)的实际选择吗？
浏览 3提问于2021-06-30得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
