问题标签 [mergesort]

我需要使用合并排序对链接列表进行排序。我已经把这段代码放在一起，但我遇到了一个奇怪的错误。

我的链表由随机数填充。但是，排序后，它只显示大于链表第一个元素的数字，按排序顺序显示。

这是我的一些代码：

对于赋值，我们要在 C 中编写归并排序函数：

我已经编写了代码并且可以运行，但是它的运行时O(N^2*log[N])违背了合并排序的目的。效率低下的原因是因为merge部分如下：

其中ct1是左列表ct2的计数器， 是右列表的计数器，array 是指向数组的指针。两者ct1和ct2最初都设置为零。就像我说的，这行得通，只是效率低下，因为你必须改变一切。我想在排序之前将子数组拆分为两个临时数组，但是您应该无法创建长度未定义为常量的数组。我还应该注意，虽然我可以使用辅助函数，但我不能更改函数参数：必须有一个指向数组的指针和长度。

对于一个类分配，我需要使用它的迭代器来对一个向量进行合并排序。

我编写了以下适用于向量但不使用迭代器的代码：

我尝试进行一些更改以适应迭代器，但它不允许我在迭代器上执行诸如 < 和 + 之类的操作。

如何在我的归并排序中适应迭代器的使用？

仅供参考，这些是我使用的 typedef：

我是否正确地说，在这两种算法中，您所做的只是获取您的结构，递归地将其分成两部分，然后以正确的顺序构建您的结构？

那么区别是什么呢？

编辑：我找到了以下用于在快速排序中实现分区的算法，但我真的不明白它是如何工作的，特别是(hi + low) >>> 1用作参数的 swop 行！任何人都可以理解这一点吗？

以下代码对单词数组进行排序，处理小数组，并对大数组进行分段（> 400000 个单词，尽管我没有找到限制）。它被一个程序调用，该程序将一个单词数组（从文件中读取）传递给它以进行排序并测试其是否成功：

每次运行此代码时，我都会遇到运行时错误，算法似乎是正确的，我使用长值而不是整数，因为数组的大小很大。

那么似乎是什么问题？

提前致谢

娜塔莉;

在 Quicksort、MergeSort 和 Binary Insertion Sort 中，是否有过使用其中任何一种的情况？

我知道像快速排序这样的东西在几乎排序的列表上可能会出现问题（但我相信枢轴的随机分配可以消除最坏情况的时间），所以使用 MergeSort 可能会更好。MergeSort 可能比 QuickSort 使用更多空间，我不完全确定，Merge 可能更适合 LinkedLists。

而且我猜二进制插入排序更适合较小的列表？如果是这样，是否有使用此阈值的阈值，还是仅留给解释的大小？比如，如果列表大小为 3，我们应该使用二进制插入排序而不是快速还是合并？

我有一个二维数组，表示构成矩形的点网格的 x 和 y 坐标。使用的数据集通常非常大。我想对从左上角开始并沿平行对角线移动直到右下角的点进行排序。我正在使用 Arrays.sort 函数和以下比较器来执行此操作：

当每个点的 x 和 y 坐标间隔两位数时，该代码由于某种原因起作用，但如果它们仅间隔一位数，则排序中会出现错误。

可以在此处找到原始订单的示例： http ://www.mediafire.com/?slq73v3zn2zs98l

可以在此处找到生成的排序列表的示例： http ://www.mediafire.com/?x8f08q0qoof398w

为什么排序不起作用？非常感谢任何帮助！

我正在寻找一种可以学习和理解合并排序的简单方法。我在网上查看过，发现合并排序对单链表非常有用，但我不明白该怎么做。这是我找到的网站： Wikipedia Merge sort and Specific linked lists

我不确定要给你什么代码。我基本上只是在我的头文件中有这个并且是新手，所以我很基础。提前谢谢你的帮助 ：）

哦亲爱的; 我似乎误会了这一点。

我想将一个单链表拆分 10,000 次，但显然（在你们帮助我之前我不知道这一点）它会导致堆栈溢出。

我对此真的很陌生，所以有什么办法我仍然可以做到这一点并且不会导致堆栈溢出？使用参考还是什么？

这是方法：