嗯，几天前我问了一个关于排序的问题。我发现了如何通过对8个元素进行排序来证明最少的比较次数是16，我理解其中的原因。但是我的合并排序算法计算了17次比较，在我的例子中它是正确的。为了合并两个长度分别为x和y的有序数组，我们需要(x+y)-1个比较，所以在合并排序中，我们得到17个比较。但必须有16次比较才有可能，所以..多么?我可以在哪里保存1个比较)。
这是一张图片：
谢谢!
浏览 0提问于2011-12-31得票数 8
回答已采纳
2回答
我开始理解当排序时，比方说LinkedList，最好使用合并排序，因为当你想把一些东西放在列表的中间时，你需要O(1) (常量)时间和O(1)内存。因此，可以在不占用额外空间的情况下进行合并排序。
我的问题是:应该在ArrayList上使用哪种排序算法？排序的数据类型重要吗？
如果我对LinkedList的理解是错误的，请纠正我，或者让我知道我是否遗漏了什么(例如，使用merge的一些参数)。
浏览 1提问于2018-02-20得票数 0
大多数排序算法的复杂度为O(N_N)或O(N_logN)来实现result.However，对于特定的输入集，有些算法的复杂度为O(N)，我想知道在所有情况下，是否都有一个复杂度为O(N)的排序算法。
浏览 3提问于2014-10-28得票数 2
回答已采纳
1回答
我正在尝试编写一个方法来比较四种不同排序算法(合并排序、快速排序、堆排序、插入排序)的运行时间。我尝试在for循环的每次迭代中对每个算法进行计时，这会增加随机生成的array each循环的数组大小。我的代码工作正常，但是花费了太多的时间。在循环结束时，我计算了每个排序算法接管大小为1到100的数组的平均时间。
注意: generateArray( num )只是创建一个填充了大小为num的随机整数的数组。
我不是一个伟大的程序员，有什么方法可以更好地实现它呢？
下面是代码片段：
static void testArrays() {
ThreadMXBean bean = Manage
浏览 0提问于2018-03-25得票数 0
7回答
想象一下这样一种情况，两个元素的比较非常昂贵。
你会使用哪种排序算法？
在平均情况下，哪种排序算法使用的比较最少？
如果你可以期望很多比较的元素是相同的，比如在80%的比较中。有什么不同吗？
浏览 3提问于2012-10-27得票数 20
回答已采纳
16回答
对于绝对最坏的情况，已知的最快排序算法是什么？我不关心最好的情况，假设有一个巨大的数据集，如果这很重要的话。
浏览 0提问于2009-04-21得票数 4
1回答
是否有客观的测试来为特定类型的列表找到最佳排序算法？我试过这样的测试，但不确定它是否可靠。关键可能是:能否设计出一个客观的测试来概括最优的列表类型，或者，这些决定是否需要经验证据？
问题
我试图为特定类型的列表找到最佳排序算法。它们包含2-202个具有唯一整数的项。我正试图找到最快的方法来对数百万这样的名单进行排序。
当我注意到C sorted(unsorted)中内置的test用于Python的速度仅略快于我在python中的简单测试simple_sort(unsorted_set, order)时，这个搜索就开始了。有趣的是，Python中的quick_sort并不总是比simple_so
浏览 3提问于2015-06-18得票数 2
回答已采纳
1回答
我试图找到一个大理石问题的下界，问题是；
有n个弹珠，可能有1个弹珠比其余的弹球轻，也可能它们都相等。
我从标准加权问题中知道，找到较轻的大理石的下限是O(log3 n)。
然而，在这种情况下，可能是所有弹珠都相等的情况，这会改变下限吗？
那么，下界是否等于它可以求解的最佳情况？
浏览 0提问于2012-03-12得票数 1
回答已采纳
3回答
对于运行速度比O(n log n)快的泛型元素(不像计数排序或桶排序)，有没有什么实用的算法？
浏览 0提问于2011-02-12得票数 17
回答已采纳
1回答
优化少量数据的插入排序
、、、
我正在构建一个混合排序，为此，我需要一个快速和自适应的排序理想的小规模(< 65个元素)。
插入排序立即浮现在脑海中，我一直在修补不同的实现。我的要求是按照C++标准接受迭代器。
线性插入排序
template <typename Iter>
void lin_sort(Iter begin, Iter end) {
for (auto cur = begin; cur != end; ++cur) {
auto key = *cur;
auto ins = cur - 1;
for (; begin <= ins
浏览 0提问于2014-11-28得票数 4
回答已采纳
3回答
我们有3种不同的合并排序。
自上而下
自下而上
天然
这些自适应算法中的任何一个吗？例如，如果数组被排序，它们将利用排序顺序。
据我所知，无论数组是否已排序，合并排序仍将进行比较，然后进行合并。所以，答案是这些都不是适应性的。
我的理解正确吗？
浏览 17提问于2014-05-13得票数 1
1回答
首先，我将提供代码的链接：
在我的英特尔酷睿2 Duo上，PHP 5.4.6结果是：
usort: 7.8763520717621
quicksort: 2.9220938682556
(usort比quicksort慢)
但在Ideone上的结果是：
usort: 0.0313699245453
quicksort: 0.0621209144592
(usort比quicksort更快)
我也在朋友的电脑上检查过代码(Intel Core i5，PHP5.4.4)，usort也更快。
我的问题是:为什么有时候快速排序比usort快，有时候usort更快？
浏览 1提问于2012-08-26得票数 6
5回答
我正在寻找一种比Arrays.sort()性能更好的算法。我知道这看起来像一个愚蠢的问题被问了几百万次，但请继续读。
让我们有两个实现Comparable的类，它们的自然排序是基于int值的。第一个compareTo方法如下所示：
public int compareTo(ComparableInteger o) {
return this.value - o.value;
}
第二个问题是：
public int compareTo(ComparableInteger o) {
if (this.value > o.value) {
浏览 6提问于2015-02-06得票数 4
回答已采纳
5回答
很多排序算法都是基于数字的比较。如果我正确理解，当我们对字母排序使用比较算法时，我们会根据它们的值比较字符代码(它们的整数表示)和排序。(这就是为什么在ASCII表中，字母B有比A更大的代码)。但是在这个比较中，我们只按第一个字母排序，而不是整个单词。当我们在db query和ORDER BY一起使用时，我们得到了整个单词的排序。(据我所知，其原因是db后台机制，如索引等)。我还听说过Radix sort (对不起，但以前从未使用过)，正如我所见，它可以帮助按字母顺序排序(也许我错了)。
用哪种算法对单词进行排序比较好？
不正确的：
Adam
Aaron
Antony
正确：
Aaron
Ad
浏览 10提问于2013-11-25得票数 5
回答已采纳
3回答
我目前正在研究排序算法。我研究过快速排序算法依赖于数据的初始组织。如果对数组进行排序，则快速排序将变得更慢。是否还有其他类型的数据依赖于最初的数据组织？
浏览 5提问于2014-04-03得票数 0
回答已采纳
在7项比较中有一种对5项进行排序的算法:如果对5项进行调用， std::sort()会使用该算法吗？这个算法能扩展到7个条目吗？在C/C++中对7个整数排序最快的算法是什么？
浏览 6提问于2015-07-17得票数 5
回答已采纳
给定的选项：
(a) O(2N)
(b) O(N)
(c) O(logN)
(d) O(n^2)
我在网上考试中遇到过这个问题。他们提到的正确选项是O(logN)。但在我看来，它应该是O(2N)，因为他们给出的"n^2“，"n”是小写的，否则它应该是O(N^2)。谁来帮我找出正确的答案。
浏览 0提问于2017-05-24得票数 1
回答已采纳
我正在寻找一种快速的构造算法。我更感兴趣的是实现的简易性和原始速度，而不是渐近复杂性(我知道后缀数组可以通过后缀树的方式在O(n)时间内构造，但这需要大量的空间；显然，其他算法具有糟糕的最坏情况大O复杂度，但在实践中运行得相当快)。我不介意生成LCP数组作为副产品的算法，因为我自己也需要一个LCP数组。
我找到了一个，但它已经过期了。我听说过、和，但我真的不知道它们之间的比较，也不知道是否有更好的算法。考虑到后缀数组字段现在看起来是多么热门，我预计自发布以来，其他一些算法已经取代了那些算法。我似乎记得曾经看到过一篇论文，描述了一种名为"split“的快速算法，但我现在找不到它了。
那么
浏览 0提问于2011-10-22得票数 41
回答已采纳
4回答
O(nlogn)就地排序算法
、、、、
这个问题是在我的计算机科学入门期中考试准备的。
有一种算法可以在O(n)时间内找到列表中的kth元素，并假定它已经就位。使用该算法，编写一个在最坏情况下运行的就地排序算法O(n*log(n))，并证明了它的有效性。既然这个算法存在，为什么还会使用mergesort呢？
我假设我必须编写一些快速排序算法的替代形式，这是O(n^2)的最坏情况，因为合并排序不是就地算法。让我困惑的是在列表中找到kth元素的给定算法。通过数组的元素进行简单的循环迭代不是一个O(n)算法吗？
如果所提供的算法不改变执行时间内的任何内容，它如何能使排序算法的运行时间有任何不同？我不知道如何使用快速排序，插入排序或
浏览 3提问于2015-10-21得票数 2
2回答
是否有一个线性О(n+m)时间算法仅求给定图G(V,E)的最小生成树的值r？我们不想找到MST，只是它的边之和。
我一直在寻找问题的解决方案，但是Kruskal和Prim的算法由于其使用的比较结构(UnionFind(Kruskal)和PQ(Prim))而具有更高的复杂性。此外，他们还找到了MST，这是不想要的，也许还有更快的方法只找到r。
浏览 6提问于2016-02-04得票数 1
回答已采纳
3回答
人们普遍认为，对于足够小的数组，插入排序是最好的。例如，对最多64个元素的数组使用(二进制)插入排序；来自：
一些分而治之的算法，如快速排序和合并排序，通过递归地将列表划分为较小的子列表，然后排序。在实践中，这些算法的一个有用的优化是使用插入排序来排序小的子列表，因为插入排序优于这些更复杂的算法。插入排序具有优势的列表的大小因环境和实现的不同而不同，但通常在8-20个元素之间。
这是真的吗？还有更好的选择吗？
如果这在很大程度上取决于平台，我对.NET最感兴趣。
浏览 6提问于2009-08-14得票数 4
回答已采纳
1回答
以游戏的形式，对现实生活中的问题做了一些修改：
假设有一组元素{1，2，…，n}。玩家A已经选择了这个集合的单个排列。玩家B想要找出元素的顺序，通过问形式的问题“X在排列中比Y早吗？”，其中X和Y是集合的元素。
假设B想要最小化问题的数量，他需要问多少次，算法是什么？
浏览 0提问于2013-11-02得票数 2
回答已采纳
1回答
快速问题--为什么下面的查询使用了哈希匹配？ BusinessentityID是Int类型的，在这一点上我不能真正解释为什么他们需要使用哈希？ 像这样的简单数组合并不是更快吗？ 虽然我猜它在连接子句中使用不同的数据类型时是有意义的，例如GUID？ ?
浏览 11提问于2018-12-27得票数 0
2回答
我正在研究排序算法。基排序被声明为非比较排序，但它比较数字中的数字并对它们进行排序。有人能告诉我非比较排序实际上是什么意思吗？
浏览 4提问于2014-09-11得票数 6
我们本可以用哈希表来解决我们的问题，但是由于技术上的原因，我们需要在一个非常大的数组上执行排序，这是我在这里不开发的(这是针对学生项目)。
因此，我的问题是:假设您有一个非常大的数组，它只包含少量不同的值。(例如，由以下Ruby代码生成的数组：a = []; 10.upto(20) { |i| a += [i]*500_000 }; a = a.shuffle)
在这种情况下，有没有一种性能更好的算法？
浏览 5提问于2022-03-19得票数 -1
3回答
气泡排序算法实现
、、
问题描述
刚才我正在学习C++编程语言，我决定通过编写代码来做到这一点。我尝试编写一种算法，将数组中的项排序，从min值开始到max值，这样我就得到了如下所示的整数数组
int arrayToSort[] = {3,5,3,1,8,7,2,4};
并尝试编写一个算法来对这个数组进行排序。下面您可以看到源代码
算法I
int arrayToSort[] = {3,5,3,1,8,7,2,4};
int arrayToSortSize = sizeof(arrayToSort)/sizeof(int);
for(int i=1; i<arrayToSortSize; ++i) {
浏览 1提问于2013-03-05得票数 1
回答已采纳
为什么？它是更快还是更高效？
对于只有一个核心的系统，我们可以使用快速排序。我们应该在具有两个核心、四个核心或八个核心的系统上使用什么？
浏览 65提问于2010-11-29得票数 23
回答已采纳
6回答
我正在做一个项目，在这个项目中，我需要把数据插入向量中，排序并搜索.
我需要最快的算法来排序和搜索..。我一直在搜索，并发现std：：排序基本上是快速排序，这是最快的排序之一，但我不知道哪种搜索算法是最好的？双元搜索？？你能帮我吗？tnx ..。我有三种方法：
void addToVector(Obj o)
{
fvector.push_back(o);
}
void sortVector()
{
sort(fvector.begin(), fvector().end());
}
Obj* search(string& bla)
{
//i would write bin
浏览 8提问于2014-05-08得票数 8
回答已采纳
我正在编写一个程序，它只使用一个for循环N次，并对N个元素进行排序。我只想问一句，这值得吗？因为我知道它会起作用，因为它在纸面上工作得很好。它还使用比较。我还想知道基数排序是否有任何缺点。干杯。
浏览 6提问于2015-04-27得票数 1
1回答
寻找复杂度的上下限
、、、、
我想找到这个算法复杂度的下界和上界。
1: for all i=1 to n*n do
2: for all j=i to 2*i do
3: output “hello world”
4: end for
5: end for
将其写成求和并简化为
f(n) = 0.5*n^4 + 1.5*n^2
复杂度的上限似乎是O(n^4)，因为0.5*n^4是最重要的元素。
对于复杂性的下限，我使用了以下公式
f(n) = Ω(g(n)) if f(n) >= c * g(n), where c > 0
对于0<c<1，它的下界似乎是Ω(n^3)
我的推理对这两
浏览 3提问于2018-05-02得票数 0
2回答
在这里教授说，比赛排序需要(n-1) + 2(n-1)logn比较。
{其中(n-1)用于计算最大值或表示创建竞赛结构，2(n-1)logn用于其他元素排序}
为什么教授忽略了找到最小值所需的比较数？因为要计算最小元素，我们需要(n/2-1)比较。
这里logn的意思是指向基2的log n。
我正在看NPTEL讲座https://youtu.be/NU77XIX-wro (视频时间- 25:50)
浏览 0提问于2017-08-11得票数 -1
2回答
我的MySQL表中有一个char(1)类型的字段，基本上只能有m或f的值。它的当前排序规则设置为ut8_unicode_ci。我在想，我是否应该将排序规则更改为更简单的东西，比如拉丁语，因为从来不会使用完整的utf8字符集-只有字符m或f。这会改变什么吗？
浏览 0提问于2011-06-14得票数 1
回答已采纳
2回答
与桶排序相比，Swift的sort()的基准测试是timsort：
项目的数量
10,000 / 0.0403秒x6.9
0.494秒x 0.059秒x8.4
1,000,000 x6.2秒x9.1
10,000,000 / 42秒x8.2秒x5.1
100,000,000 x 506秒
机器: iMac Pro (2017)，3.2 GHz Intel Xeon W.值为硬编码的self.max()__。所提供的代码工作时间稍长。
为什么编程语言(包括Swift)不使用更快的桶排序？
import Foundation
extension Array where
浏览 0提问于2019-05-12得票数 0
回答已采纳
2回答
我最近一直在课堂上学习基本排序(冒泡排序、插入排序和选择排序)，对运行时间感到有点困惑。
在老师给我们布置的一份家庭作业中，有一个问题问道：“对于所有键相同的文件，3种基本排序中哪种排序运行得最快?对于数据顺序相反的文件呢？”
对于问题的第一部分，我不完全确定他们所说的“键”是什么意思。那么，这是否意味着有一个大小为1的数组包含多个数据？我不认为“key”和"data“是一样的。我知道如果所有的数据都是有序的，那么插入排序将是最快的，但我不确定这是否会对问题产生任何影响。
对于问题的第二部分，我认为它应该是选择排序，因为无论数据中有多少次倒置，这都需要恒定的比较次数。插入排序和冒泡排序
浏览 1提问于2014-04-15得票数 2
3回答
我已经用C语言编写了一些排序方法，我想找出程序最优的输入大小(即)分析每个算法。但是我该怎么做呢？我知道每种方法都要计时，但我不知道如何才能找到它“最佳”的大小。
浏览 1提问于2011-06-07得票数 0
回答已采纳
2回答
我有一个要排序的数组，它包含带有文件扩展名的图像，文件名是数字，文件扩展名显然是字符串。
$files = array();
$files[] = '4.jpg';
$files[] = '14.jpg';
$files[] = '1.jpg';
$files[] = '44.jpg';
如果我使用sort()，那么我会得到以下结果：
sort($files);
print_r($files);
Array
(
[0] => 1.jpg
[1] => 14.jpg
[2] => 4.jp
浏览 0提问于2010-07-24得票数 1
回答已采纳
为什么Bucket sort被认为是一种非基于比较的排序算法(不执行键比较来对列表进行排序)，而用于对单个Bucket进行排序的插入sort是基于比较的？
浏览 2提问于2021-04-04得票数 0
考虑两个k位数(以二进制表示)：
$$A = A_1 A_2 A_3 A_4 ... A_k $$
$$B = B_1 B_2 B_3 B_4 ... B_k $$
为了进行比较，我们从左到右扫描，查找0的出现，如果该数字也是0 (对于两个数字)，则检查相反的数字，注意如果发现这样的情况，则0的源小于1的源。但是如果数字是：
111111111111
111111111110
显然，这将需要扫描整个数字，如果我们事先没有被告知任何关于数字的信息，然后简单地给出它们：
比较需要$O(k)$时间。
因此，当我们查看排序方法的代码时，例如高性能的快速排序：
HPQuicksort(list): T
浏览 0提问于2014-02-14得票数 1
1回答
我正在为Web第三版阅读JavaScript，我被困住了这是如何工作的。我理解比较函数是如何工作的。但是values.sort(比较)；把我搞糊涂了。比较两个参数并比较它们。但我没有提出两个论点。即使我确实向函数传递了2个参数，它如何与Array中的其余项进行比较？排序函数在后台做了一些我不知道的事情吗？如果是的话，它是如何工作的？(预先谢谢:)
function compare(value1, value2)
{
if (value1 < value2) {
return 1;
} else if (value1 > value2) {
return -1;
}
浏览 2提问于2015-11-07得票数 1
回答已采纳
警告:合同代码大小超过24576字节(假龙中引入的限制)。此合同不得部署在主机网上。考虑启用优化器(具有较低的“运行”值！)、关闭还原字符串或使用库。
浏览 0提问于2023-01-26得票数 1
2回答
在这个中，我看到堆排序和合并排序对包含随机数的数组最有效。但是，如果我们将这些排序算法与基和内排序算法进行比较呢？
简而言之，哪种排序算法最适合对由随机数组成的数组进行排序？
谢谢
浏览 2提问于2018-09-23得票数 0
4回答
我有一个由64个结构组成的数组，它们保存了相当数量的数据(结构大约是128个字节，所以需要重新排列的是8192个字节)。该数组需要根据每个结构中的单个无符号字节进行排序。我的数据有一个有趣的属性，那就是很可能会有很多重复的排序值--这意味着如果去掉了所有重复项，数组可能只有10个唯一的元素长度，但这并不是给定的。
排序后，我需要创建一个堆栈来存储每个唯一字节运行开始的大小和类型:因此，如果我以排序的值结束:4，4，4，9，9，9，9，14，14，堆栈将是：(4,3)，(9,5)，(14,2)
我认为在这些条件下我可以执行一些很好的优化。如果我做heapsort，我可以在排序时创建堆栈，但这会比
浏览 2提问于2011-01-24得票数 1
下面是Scala中的一个文本快速排序实现。在比较quickSortRecursive和java.util.Arrays.sort()的执行时间时，我发现java.util.Arrays.sort在大型数组上要快一个数量级。有人能提示一下性能差异的原因吗？
def quickSortRecursive(list: Array[Int])(low: Int=0, high: Int=list.length-1): Unit = {
if (low<high) {
swap(list,Random.nextInt(high),high)
val pivot = partit
浏览 1提问于2014-05-06得票数 1
12回答
我想知道对此最快的算法是什么。我有8个介于0和3000之间的整数，我需要对它们进行排序。虽然只有8个整数，但这个操作将被执行数百万次。
浏览 0提问于2011-01-23得票数 10
3回答
我现在正在学习不同类型的排序，我发现，从某一点开始，我的QuickSort算法根本不起作用。
这是我的代码：
class QuickSort
{
// partitioning array on the key so that the left part is <=key, right part > key
private int Partition(int[] arr, int start, int end)
{
int key = arr[end];
浏览 5提问于2011-01-20得票数 3
问题是：
以最小的时间复杂度将k排序数组与n个元素合并到一个大小为nk的数组中。该算法应该是一个基于比较的算法。不应对输入作出任何假设。
因此，我知道有一种解决nklogk时间复杂性问题的算法，如这里所提到的：。
不过，我的问题是，我们能不能比nklogk少排序，这意味着，运行时是o(nklogk)。
于是我在网上搜索并找到了这样的答案：
它声称将一个大小为K的数组划分为单个数组，并将它们合并到一个数组中。但是这是不正确的，因为人们可以说他找到了一种解决sqrt(n)klogk问题的算法，即o(nklogk)但是n=1，所以我们在KlogK时间对数组进行排序，这与数组排序的下限并不矛盾
浏览 5提问于2022-05-22得票数 0
2回答
我试图使用vhdl对一个8位数字数组进行排序。我试图找出一种优化延迟的方法，另一种方法是使用较少的硬件。
数组的大小是固定的。但我也有兴趣将功能扩展到可变长度。到目前为止，我遇到了3种算法：
Bathcher并联
绿色排序法
Van Vorris排序
这其中哪一个能做得最好？还有什么其他的方法我应该考虑吗？谢谢。
浏览 2提问于2013-03-17得票数 2
回答已采纳
5回答
最快排序技术
、、
在过去的几天里，我一直在尝试各种排序算法。从1) O(n^2)时间复杂度的排序算法开始2) O(n log n)时间复杂度的就地和非就地排序技术
我想知道是否有排序算法可以在线性时间或更短的时间内排序。我听说过基数排序，在最好的情况下，它接近线性时间排序，具有一定的空间复杂性。有没有人能开导我？
浏览 2提问于2012-05-16得票数 3
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
