问题标签 [quicksort]

我删除了代码，因为它是家庭作业。如果您确实需要帮助，您可以查看我与 George B 的讨论（如下），或 PM 我。

嗨，大家好。这是一个家庭作业。我已经针对其他排序算法对其进行了测试，QS 是唯一在某些随机输入上崩溃的算法。

该程序退出时间很长（与其他东西一起），但输入是随机生成的......

我花了几个小时跟踪代码，仍然无法找出任何错误.... QS 对于专业人士来说可能很容易，所以我希望收到有关此实施的建议....

任何输入表示赞赏！

问：什么是“随机”？

A：包含了一部分生成。

问：什么样的错误？

好吧，我没有收到编译错误。没有QS，我可以毫无问题地运行其他四种排序算法（我可以连续运行排序）。QS启动后，程序运行一两三遍，甚至第一次运行，程序就结束了（我用的是Eclipse，所以控制台就结束了）。

输入元素的数量，或者一个负数退出：5 {一些数组}

选择排序耗时 0 秒。合并排序耗时 0 秒。快速排序耗时 0 秒。堆排序耗时 0 秒。桶排序耗时 0 秒。{5 个排序数组的输出}

输入元素的数量，或负数退出：6 {一些数组}

选择排序耗时 0 秒。合并排序耗时 0 秒。快速排序耗时 0 秒。堆排序耗时 0 秒。桶排序耗时 0 秒。

{5 个排序数组的输出}

输入元素的数量，或者一个负数退出：8 {arrays} --- 控制台结束---

同样，问题是它经常崩溃，所以这表明访问冲突的可能性很高，但是进行 10 多次跟踪我没有看到问题......（也许我的大脑堆栈超载 - _ - )

谢谢。

我在 c# 中编写了我的快速排序算法，但它有一个问题，当我编译它时，它在某些情况下不起作用，例如当我在 textbox6 中输入数字 12、32、11 进行排序时，当我转到时它给出超出范围的错误跟踪它，调试器显示 num[] 取了 nums[0]=12,nums[1]=11,nums[2]=1

编辑： 我更改了 while 条件，它知道不会给出超出范围的错误，但是当输入为 12、32、11 时，输出 11、12、1

我正在练习编写排序算法作为一些面试准备的一部分，我想知道是否有人可以帮助我找出为什么这种快速排序不是很快？它似乎具有正确的运行时复杂性，但它比我的合并排序慢约 2 的常数因子。我也将感谢任何可以改进我的代码但不一定回答问题的评论。

非常感谢你的帮助！如果我犯了任何礼仪错误，请不要犹豫，让我知道。这是我在这里的第一个问题。

非常感谢，所有帮助过的人！

这是我为后代改进的课程：

我想编写一个快速排序函数，按“num”升序对“bar”数组进行排序。不太确定什么是最好的方法，因为我从来没有写过快速排序。我查看了一些示例代码，但我看不到如何针对这种情况修改它们。通过将指针传递给数组的第一个和最后一个元素来完成的就地排序不起作用，因为这只会对“num”成员进行排序，而不是对整个对象进行排序。将对象数组拆分为一个较低的数组、一个枢轴和一个较高的数组并递归排序每个看起来很有希望，但我不确定传递值将如何工作......

非常感谢任何帮助。抱歉，如果之前有人问过这个问题。

快速排序算法的平均时间复杂度为 O(n*log(n))，最坏情况复杂度为 O(n^2)。

假设 Hoare 的快速排序算法有一些变体，什么样的输入会导致快速排序算法表现出最坏情况的复杂性？

请说明与特定快速排序算法（例如枢轴选择等）的实现细节相关的任何假设，或者它是否来自诸如 libc 等常用库。

一些阅读：

1. 快速排序的杀手锏
2. 快速排序是最优的
3. 设计一个排序函数
4. 内省排序和选择算法

我现在正在学习不同类型的排序，我发现从某个点开始，我的 QuickSort 算法根本没有那么快。

这是我的代码：

在包含一百万个元素的数组上运行此代码大约需要 15 秒。例如，MergeSort 或 HeapSort 在不到一秒的时间内完成相同的操作。

你能向我解释为什么会发生这种情况吗？

我正在尝试在 Java 中实现几种排序算法，以比较性能。根据我的阅读，我期望 quickSort 比 mergeSort 更快，但在我的代码中它不是，所以我认为我的 quickSort 算法一定有问题：

结果（在 0 到 1500000 之间的 100 万个整数上）：

mergeSort（也用 arrayList 实现）：1.3sec（平均）（0.7sec 用 int[] 代替）

快速排序：3 秒（平均）

只是我的支点选择不好，还是算法中也存在一些缺陷。

另外，有没有更快的方法用 int[] 而不是 ArrayList() 来编码？（如何声明更大/更小数组的数组大小？）

PS：我现在可以以就地方式实现它，因此它使用更少的内存，但这不是重点。

编辑 1：我通过更改 concat 方法赢得了 1 秒。谢谢！

快速排序算法何时需要 O(n^2) 时间？

我正在对大量数据进行快速排序，为了好玩，我试图将其并行化以加快排序速度。但是，在当前形式中，由于同步阻塞点，多线程版本比单线程版本慢。
每次我生成一个线程时，我都会在一个 int 上获得一个锁并递增它，每次线程完成时我都会再次获得一个锁和递减，此外还要检查是否有任何线程仍在运行（int > 0）。如果没有，我会唤醒我的主线程并处理已排序的数据。

我确信有更好的方法来做到这一点。虽然不确定它是什么。非常感谢您的帮助。

编辑：我想我没有提供足够的信息。
这是一个八核 Opteron 上的 Java 代码。我不能切换语言。
我正在排序的数量适合内存，并且在调用快速排序时它已经存在于内存中，因此没有理由将其写入磁盘只是为了将其读回内存。
“获得锁”是指在整数上有一个同步块。

我将为学生实现一个玩具磁带“大型机”，展示“快速排序”类函数的速度（递归与否，并不重要，因为硬件速度慢，以及众所周知的堆栈反转技术） “冒泡排序”函数类。所以，虽然我很清楚硬件实现和控制器，但我猜快速排序功能在序列、顺序和比较距离方面比其他功能快得多（从中间倒带比从非常最后，由于不同的倒带速度）。

不幸的是，这不是真的。与“快速排序”函数相比，这个简单的“冒泡”代码在比较距离、方向以及比较和写入的数量方面显示出很大的改进。

所以我有3个问题：

1. 我在执行快速排序功能时是否有错误？
2. 我在实施 bubblesoft 功能时是否有错误？
3. 如果不是，为什么“冒泡排序”函数（比较和写入操作）比“快速排序”函数快得多？

我已经有一个“快速排序”功能：

我有自己的“冒泡排序”功能实现：

我在测试示例代码中使用了这些排序函数，如下所示：