我在接受采访时被问到这个问题.他们都是O(nlogn),但大多数人使用Quicksort而不是Mergesort.这是为什么？
我找到了一种在quicksort中更有效地处理重复元素的方法,并且想知道是否有人之前已经看过这个.
这种方法大大减少了检查重复元素所涉及的开销,这有助于在有和没有重复元素的情况下提高性能.通常,重复的元素以几种不同的方式处理,我将首先列举.
首先,有荷兰国旗方法对数组进行排序[ < pivot | == pivot | unsorted | > pivot].
其次,有一种方法是在排序过程中将相等的元素放在最左边,然后将它们移动到排序中心[ == pivot | < pivot | unsorted | > pivot],然后在排序后将==元素移动到中心.
第三,Bentley-McIlroy分区将==元素放在两边,以便排序[ == pivot | < pivot | unsorted | > pivot | == pivot],然后==元素移动到中间.
最后两种方法是为了减少开销.
现在,让我解释一下我的方法如何通过减少比较次数来改进快速排序.我一起使用两个quicksort函数而不是一个.
我将调用的第一个函数q1,它将数组排序为[ < pivot | unsorted | >= pivot].
我将调用的第二个函数q2,它将数组排序为[ <= pivot | unsorted | > pivot].
现在让我们一起看看它们的用法,以便改进重复元素的处理.
首先,我们调用 …
我有一个文件(大小= ~1.9 GB),其中包含~220,000,000(~2亿)单词/字符串.它们有重复,每100个字几乎有1个重复字.
在我的第二个程序中,我想读取该文件.我成功地使用BufferedReader按行读取文件.
现在要删除重复项,我们可以使用Set(和它的实现),但Set有问题,如下面3个不同的场景所述:
我有限制,我不能进一步增加JVM大小,我想从文件中删除重复的单词.
如果您对从这样一个巨大的文件中使用Java删除重复单词的任何其他方法/方法有任何疑问,请告诉我.非常感谢 :)
添加信息问题:我的单词基本上是字母数字,它们是我们系统中唯一的ID.因此,它们不是简单的英语单词.
我只是想知道(在一些严重的偏执和某些情况下)使用QuickSort算法是否会被视为应用程序中的安全风险.
它的基本实现和改进版本(如3-median-quicksort)都具有特定输入数据行为异常的特性,这意味着它们的运行时间在这些情况下可能会极大地增加(具有O(n^2)复杂性),更不用说堆栈溢出的可能性.
因此,我认为通过向程序提供预先排序的数据可能会造成伤害,导致算法表现得像这样,这可能会对例如多客户端Web应用程序产生不可预测的后果.
这个奇怪的案例是否值得任何安全考虑(因此会迫使我们使用Intro-或Mergesort)？
编辑:我知道有很多方法可以阻止Quicksort的最坏情况,但是语言集成排序(如.NET的3中位数)呢.他们会成为禁忌吗？
两篇文章都具有出色的可视化.
两者都具有n*log(n)复杂度.
显然,数据的分布将影响排序的速度.我的猜测是,由于比较可以快速比较任何两个值,无论它们的扩散如何,数据值的范围都无关紧要.
更重要的是,应该考虑关于排序的横向分布(x方向)(去除幅度).
如果测试数据具有一定程度的排序,那么需要考虑的一个好的测试用例......
我正在尝试创建一个非常节省空间的不寻常的关联数组实现,我需要一个满足以下所有条件的排序算法:
另请注意,要排序的数据结构是一个数组.
很容易看出有一个基本的算法匹配这三个中的任何两个(插入排序匹配1和2,合并排序匹配1和3,堆排序匹配2和3),但我不能为我的生活找到任何东西匹配所有这三个标准.
我写了一个简单的C++代码来检查数据排序的速度,以列表的形式表示,然后是矢量.
在列表的情况下,我得到时间为27秒.对于矢量,我得到10秒.为什么巨大的性能差距？用于排序列表和向量的算法不一样吗？即 归并排序？
编辑:我可能在最后一点错了.据我所知,教科书在理论上描述排序算法时,似乎是list在一个意义上使用这个词std::vector.我不知道向量的排序算法如何与列表的排序算法不同,所以如果有人可以澄清那将是非常有用的.谢谢.
//In this code we compare the sorting times for lists and vectors.
//Both contain a sequence of structs
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
using namespace std;
struct particle
{
double x;
double y;
double z;
double w;
bool operator<(const particle& a) const
{
return x < a.x;
}
};
int main(int argc, char *argv[])
{
int N=20000000;
clock_t start,stop;
vector<particle> …Java中整数数组中哪个更昂贵的操作交换或比较？或者他们都可以被认为是一样的？
上下文：对几乎已排序的数组进行排序（我不是在谈论 k 排序数组，其中每个元素从正确位置最多偏移 k）。即使我们使用插入排序，最后的比较次数也将与任何数组或最坏情况下的比较次数相同。不是吗？只是掉期会更少。如果我错了，请纠正。
在Java中,基本类型的Arrays.sort()使用快速排序.另一方面,对象的Arrays.sort()使用Merge排序.同样适用于Collection.sort(),它也使用Merge排序.集合排序使用下面的Arrays排序实现.所以,简单来说,我可以说基元是使用快速排序排序的,但是对象是使用合并排序进行排序的.
我的猜测是它与自己的排序算法有关.关于快速排序vs合并排序的SO有很多讨论,像这样和这个.似乎存在相互冲突的主张哪个更好,这是可以理解的,因为这取决于数据集.
我的理解是
Android API似乎遵循与Java相同的模式.这是我在Arrays.java中找到的
public static void sort(long[] array) {
DualPivotQuicksort.sort(array);
}
还有这个,
public static void sort(Object[] array) {
ComparableTimSort.sort(array);
}
我不明白的是,是什么让Merge排序成为在Java或Android中排序对象的好选择？为什么不把这个决定留给开发者？
对于绝对最坏情况,最快的已知排序算法是什么？我不关心最好的情况,并假设一个巨大的数据集,如果这甚至重要.
我试图在PHP中编写一个涉及小数组的基本合并排序,但问题是执行大约需要一分钟左右,并返回:
致命错误:第39行的/Users/web/www/merge.php中允许的内存大小为536870912字节(试图分配35个字节)
有没有人知道代码可能出错的地方(如果有的话)？我现在一直在盯着这个好时光.
<?php
$array = array(8,1,2,5,6,7);
print_array($array);
merge_sort($array);
print_array($array);
function merge_sort(&$list){
if( count($list) <= 1 ){
return $list;
}
$left = array();
$right = array();
$middle = (int) ( count($list)/2 );
// Make left
for( $i=0; $i < $middle; $i++ ){
$left[] = $list[$i];
}
// Make right
for( $i = $middle; $i < count($list); $i++ ){
$right[] = $list[$i];
}
// Merge sort left & right
merge_sort($left);
merge_sort($right);
// Merge left & right
return merge($left, $right);
}
function …