我在接受采访时被问到这个问题.他们都是O(nlogn),但大多数人使用Quicksort而不是Mergesort.这是为什么？
我知道问题不是太具体.
我想要的只是告诉我如何将普通合并排序转换为就地合并排序(或具有恒定额外空间开销的合并排序).
我所能找到的(网上)是"太复杂"或"超出本文范围"的网页.
唯一已知的就地合并方式(没有任何额外空间)太复杂,无法简化为实际程序.(取自这里)
即使它太复杂,如何使合并排序到位的基本概念是什么？
我在接受采访时被问及这是我提供的解决方案:
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
if (a[i] < b[j])
{
answer[k] = a[i];
i++;
}
else
{
answer[k] = b[j];
j++;
}
k++;
}
while (i < a.length)
{
answer[k] = a[i];
i++;
k++;
}
while (j < b.length)
{
answer[k] = b[j];
j++;
k++;
}
return answer;
}
有没有更有效的方法来做到这一点？ …
Java 6的Arrays.sort方法使用Quicksort作为基元数组,并对对象数组进行合并排序.我相信大多数时候Quicksort比合并排序更快,并且内存更少.我的实验支持这一点,尽管两种算法都是O(n log(n)).那么为什么不同的算法用于不同的类型呢？
我在论坛中阅读了以下内容:
合并排序对于链接列表等不可变数据结构非常有效
和
当数据存储在内存中时,快速排序通常比合并排序更快.但是,当数据集很大并且存储在外部设备(如硬盘驱动器)上时,合并排序在速度方面是明显的赢家.它最大限度地减少了外部驱动器的昂贵读取
和
在链表上操作时,合并排序只需要少量的辅助存储
有人能帮助我理解上述论点吗？为什么合并排序首选排序庞大的链表？它如何最大限度地减少对外部驱动器的昂贵读取？基本上我想了解为什么会选择合并排序来排序大链表.
我最近刷了一些基础知识,发现合并排序链表是一个非常好的挑战.如果你有一个很好的实现,那么在这里展示它.
我记得,从一开始,最流行的实现方法std::list<>::sort()是以自下而上的方式实现的经典Merge Sort算法(另请参阅是什么让gcc std :: list排序实现如此之快？).
我记得有人恰如其分地将这种策略称为"洋葱链"方法.
至少这是GCC实现C++标准库的方式(例如,参见这里).这就是旧版Dimkumware在标准库的MSVC版本中的STL,以及所有版本的MSVC到VS2013的情况.
但是,随VS2015提供的标准库突然不再遵循此排序策略.VS2015附带的库使用自上而下的 Merge Sort 的相当简单的递归实现.这让我感到很奇怪,因为自上而下的方法需要访问列表的中点才能将其分成两半.由于std::list<>不支持随机访问,找到该中间点的唯一方法是逐字遍历列表的一半.此外,在最开始时,有必要知道列表中的元素总数(在C++ 11之前不一定是O(1)操作).
尽管如此,std::list<>::sort()在VS2015确实如此.以下是该实现的摘录,它定位中点并执行递归调用
...
iterator _Mid = _STD next(_First, _Size / 2);
_First = _Sort(_First, _Mid, _Pred, _Size / 2);
_Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
...
正如您所看到的,他们只是无意中使用std::next了遍历列表的前半部分并到达_Mid迭代器.
我想知道这种转变背后的原因是什么？我所看到的是std::next在每个递归级别上重复调用看似明显的低效率.天真的逻辑说这是慢的.如果他们愿意支付这种价格,他们可能希望获得回报.那他们得到了什么？我没有立即将此算法视为具有更好的缓存行为(与原始自下而上方法相比).我没有立即看到它在预先排序的序列上表现得更好.
当然,由于C++ 11 std::list<>基本上需要存储其元素数,这使得上面的效率略高,因为我们总是提前知道元素数.但这仍然不足以证明每个递归级别的顺序扫描是正确的.
(不可否认,我没有试图相互竞争实施.也许有一些惊喜.)
我找不到任何有效的Python 3.3 mergesort代码,所以我自己做了1.有没有办法加快速度？它在大约0.3-0.5秒内排序20000个数字
def msort(x):
result = []
if len(x) < 2:
return x
mid = int(len(x)/2)
y = msort(x[:mid])
z = msort(x[mid:])
while (len(y) > 0) or (len(z) > 0):
if len(y) > 0 and len(z) > 0:
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
elif len(z) > 0:
for i in z:
result.append(i)
z.pop(0)
else:
for i in y:
result.append(i)
y.pop(0)
return result
我试图理解外部合并排序算法是如何工作的(我看到了相同问题的一些答案,但没有找到我需要的东西).我正在阅读Jeffrey McConnell撰写的"分析算法"一书,我正在尝试实现那里描述的算法.
例如,我有输入数据:3,5,1,2,4,6,9,8,7,我只能将4个数字加载到内存中.
我的第一步是读取4个数字块的输入文件,在内存中对它们进行排序,然后将一个写入文件A,然后写入文件B.
我有:
A:[1,2,3,5][7]
B:[4,6,8,9]
现在我的问题是,如果它们不适合内存,我如何将这些文件中的块合并到较大的文件中呢？杰弗里麦康奈尔写道,我需要阅读半块并将它们合并到下一个文件C和D.
但我得错了序列:
C:[1,2,4,6,3,8,5,9]
D:[7]
有人可以提供分步说明的例子吗？
PS:我理解如何通过读取文件来合并数字,但是如何使用内存缓冲区来减少I/O操作呢？