问题标签 [quicksort]

我发现这种快速排序分区方法令人困惑和错误，但它似乎有效。我指的是这个伪代码。注意：他们在文章末尾也有一个 C 实现，但它与他们的伪代码有很大不同，所以我不在乎。

我也是这样用 C 语言编写的，尽可能地忠实于伪代码，即使这意味着要做一些奇怪的 C 语言：

如果你运行它，你会得到以下输出：

1 6 2 3 4 8 7 - 5

然而，这是错误的，不是吗？显然a[5]它之前的所有值都没有低于它，因为a[2] = 6 > a[5] = 4. 更不用说7应该是枢轴（初始a[p]），但它的位置既不正确又丢失了。

以下分区算法取自维基百科：

并产生这个输出：

1 6 2 3 8 4 7 - 1

我认为这是一个正确的结果：枢轴 ( a[r] = a[7]) 已到达其最终位置。

但是，如果我在以下算法中使用初始分区函数：

...这似乎是一个正确的排序算法。我在很多随机输入上对其进行了测试，包括所有长度为 20 的 0-1 数组。

我还尝试将此分区函数用于选择算法，但未能产生正确的结果。它似乎可以工作，但是作为快速排序算法的一部分，它甚至非常快。

所以我的问题是：

1. 任何人都可以发布一个算法不起作用的例子吗？
2. 如果没有，为什么它会起作用，因为分区部分似乎是错误的？这是我不知道的另一种分区方法吗？

我对以下代码有疑问：

但是，这不适用于过多的元素（它适用于 10 000 个元素，但不适用于 100 000 个元素）。

示例代码：

STL 分区功能不适用于这样的大小吗？还是我错过了什么？

非常感谢您的帮助。

我写了一个快速排序算法但是，我想在某处进行更改，以便此快速排序将按降序输出元素。

我搜索并发现我可以将 partition() 中的比较运算符 (<) 更改为其他方式（如下所示）。

但它不工作..

如果我快速排序下面的数组，$array = (3,9,5,7);

应该：

$array = (9,7,5,3)

但实际输出是：

$array = (3,5,7,9)

下面是我的快速排序，它试图按降序输出元素。我应该如何更改以降序排序？如果您需要任何澄清，请告诉我。谢谢！

在列表被分成左右两半（小于和大于枢轴）之后，我正在使用 Pthreads 为每个分区创建一个新的线程。我递归地执行此操作，直到达到允许的最大线程数。

当我使用 printfs 跟踪程序中发生的事情时，我清楚地看到每个线程都在并行执行其委派的工作。但是，使用单个进程始终是最快的。一旦我尝试使用更多线程，完成所需的时间几乎翻了一番，并且随着线程数的增加而不断增加。

我被允许在运行它的服务器上使用多达 16 个处理器。

算法是这样的：通过将元素与枢轴进行比较，将数组拆分为左右。为左右开始一个新线程，并等待线程重新加入。如果有更多可用线程，它们可以更递归地创建。每个线程都等待其子节点加入。

一切对我来说都很有意义，并且排序工作得很好，但是更多的线程使它变得非常慢。

我尝试为要启动的线程设置每个分区的最小元素数（例如 50000）。

我尝试了一种方法，当一个线程完成后，它允许启动另一个线程，这会导致数百个线程在整个过程中启动和完成。我认为开销太大了。所以我摆脱了它，如果一个线程执行完毕，就不会创建新线程。我得到了更多的加速，但仍然比单个进程慢很多。

我使用的代码如下。

http://pastebin.com/UaGsjcq2

有人知道我做错了什么吗？

我已经编写了这段代码，但它会在控制台中打印这些堆栈跟踪，请帮助我，谢谢！（“p”和“q”分别是我们数组的第一个和最后一个索引）

堆栈跟踪：

我还将导致这些堆栈跟踪的那些语句加粗。喜欢 ==> ** ...**

编辑：

为了更容易理解，我编辑了我的帖子，它还将打印这些堆栈跟踪，并且我将导致这些堆栈跟踪的行加粗！！！

堆栈跟踪：

请帮帮我谢谢

编辑：

我已经写了这段代码，注意这篇文章的第一答案，但它不会对我的数组进行排序！！！

输出：

我需要你的帮助我真的很困惑！

我试图理解 3 路基数 Quicksort，但我不明白为什么 CUTOFF 变量在那里？和插入方法？

来自http://www.cs.princeton.edu/algs4/51radix/Quick3string.java.html

我在 C++ 中有以下代码

我有问题

请帮忙

我有一个 15000 个元素的数组，每个元素都是 4 个元素的数组。我想按 4 的第二个元素排序。最初我将原始数组的键作为第二个元素，然后进行 k 排序，但不幸的是，一些第二个元素是重复的，因为一个键不能引用多个元素我丢失了一些正在过渡的元素。我可以按第二个元素冒泡排序，但我正在寻找至少按 nlog(n) 顺序运行的东西。谁能想到一个可以按第二个元素排序的好算法（或者可能是我不知道的php函数）？谢谢！

在 a 上插入的最坏情况运行时间red-black tree是O(lg n)，如果我in-order walk在树上执行 a，我基本上会访问每个节点，因此打印排序集合的总最坏情况运行时间将是 O(n lg n)

我很好奇，为什么red-black trees不首选排序quick sort（其平均案例运行时间为O(n lg n).

我看到这可能是因为red-black trees没有就地排序，但我不确定，所以也许有人可以提供帮助。

我被分配使用随机枢轴点实现快速排序（因为它被认为是最有效/最安全的方式），但我一直在为 bogosort 苦苦挣扎。谁能指导我怎么做？有人可以帮我看看我的 bogosort 看看我是否可以保存它吗？