我知道问题不是太具体.
我想要的只是告诉我如何将普通合并排序转换为就地合并排序(或具有恒定额外空间开销的合并排序).
我所能找到的(网上)是"太复杂"或"超出本文范围"的网页.
唯一已知的就地合并方式(没有任何额外空间)太复杂,无法简化为实际程序.(取自这里)
即使它太复杂,如何使合并排序到位的基本概念是什么？
在许多情况下,快速排序比合并排序要好得多.但是,何时合并排序可能比快速排序更好？
例如,当数据无法一次加载到内存时,合并排序比快速排序更有效.还有其他案件吗？
编辑:建议的重复问题列表的答案快速排序合并排序的所有优点.我在这里询问可能的情况和使用合并排序的应用程序比使用快速排序更有利.
我昨天正在努力实现一个快速排序,然后我运行它,期望比Mergesort更快的运行时间(我也已实现).我运行了两个,虽然快速排序对于较小的数据集<100个元素更快(并且我确实验证了它的工作原理),但mergesort很快就成为了更快的算法.有人告诉我,quicksort几乎总是比mergesort"更快",我理解这个话题有一些争论,但我至少预计它会比这更接近.对于数据集> 10000个元素,mergesort的速度提高了4倍以上.这是预期的,还是我的快速排序代码中有错误？
归并排序:
public static void mergeSort(int[ ] e)
{
if (e.length <= 1) return;
int[] first = new int[e.length/2];
int[] second = new int[e.length - first.length];
System.arraycopy(e, 0, first, 0, first.length);
System.arraycopy(e, first.length, second, 0, second.length);
mergeSort(first);
mergeSort(second);
System.arraycopy(merge(first, second), 0, e, 0, e.length);
}
private static int[] merge(int[] first, int[] second) {
int iFirst = 0;
int iSecond = 0;
int iCombined = 0;
int[] combined = new int[first.length + second.length];
while(iFirst < first.length && iSecond …我只是想知道(在一些严重的偏执和某些情况下)使用QuickSort算法是否会被视为应用程序中的安全风险.
它的基本实现和改进版本(如3-median-quicksort)都具有特定输入数据行为异常的特性,这意味着它们的运行时间在这些情况下可能会极大地增加(具有O(n^2)复杂性),更不用说堆栈溢出的可能性.
因此,我认为通过向程序提供预先排序的数据可能会造成伤害,导致算法表现得像这样,这可能会对例如多客户端Web应用程序产生不可预测的后果.
这个奇怪的案例是否值得任何安全考虑(因此会迫使我们使用Intro-或Mergesort)？
编辑:我知道有很多方法可以阻止Quicksort的最坏情况,但是语言集成排序(如.NET的3中位数)呢.他们会成为禁忌吗？
我见过很多地方说quicksort是好的,因为它适合缓存相关的东西,比如维基说
此外,quicksort的顺序和本地化内存引用可以很好地与缓存配合使用
http://en.wikipedia.org/wiki/Quicksort
谁能给我一些关于这个说法的见解？quicksort如何与缓存相关？通常意味着语句中的缓存是什么意思？为什么quicksort更适合缓存？
谢谢
我在互联网上找到了这个代码,它是用于数组,我想改为双链表(而不是索引我们应该使用指针)请你帮我,我怎么能改变合并方法(我改变了排序方法)我自己)这也不是我的家庭工作,我喜欢使用链表!
public class MergeSort {
private DoublyLinkedList LocalDoublyLinkedList;
public MergeSort(DoublyLinkedList list) {
LocalDoublyLinkedList = list;
}
public void sort() {
if (LocalDoublyLinkedList.size() <= 1) {
return;
}
DoublyLinkedList listOne = new DoublyLinkedList();
DoublyLinkedList listTwo = new DoublyLinkedList();
for (int x = 0; x < (LocalDoublyLinkedList.size() / 2); x++) {
listOne.add(x, LocalDoublyLinkedList.getValue(x));
}
for (int x = (LocalDoublyLinkedList.size() / 2) + 1; x < LocalDoublyLinkedList.size`(); x++) {`
listTwo.add(x, LocalDoublyLinkedList.getValue(x));
}
//Split the DoublyLinkedList again
MergeSort sort1 = new MergeSort(listOne);
MergeSort sort2 …我写了一个简单的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> …我想知道我们是否能以某种方式修改快速排序算法以产生O(n logn)的最坏情况时间复杂度.虽然这可以通过置换数据然后假设我们将得到平均情况复杂度而不是最坏情况来完成.但这不是一个完整的证明解决方案,因为我们可以在置换后再次陷入最坏的情况.你有什么别的建议吗？