问题标签 [quicksort]

假设您有一个n包含随机生成元素的大小数组，并且您想使用快速排序对数组进行排序。对于足够大的 n（比如 1,000,000），为了加快快速排序，当数组变得足够小时停止递归并改用插入排序是有意义的。在这样的实现中，快速排序的基本情况是 some value base > 1。选择的最佳基值是多少，为什么？

我正在研究基于Select 算法的快速排序变体实现的快速排序变体实现，以选择一个好的枢轴元素。传统的智慧似乎是将数组划分为 5 个元素块，取每个块的中值，然后递归地对生成的中值应用相同的块方法以获得“中值的中值”。

让我困惑的是选择 5 元素块而不是 3 元素块。对于 5 元素块，在我看来，您执行n/4 = n/5 + n/25 + n/125 + n/625 + ...的是 5 的中位数操作，而对于 3 元素块，您执行n/2 = n/3 + n/9 + n/27 + n/81 + ...的是 3 的中位数操作。由于每个 5 的中位数是 6 次比较，每个 3 的中位数是 2 次比较，这导致3*n/2使用 5 的中位数和n进行比较和使用中位数 3 进行比较。

谁能解释这种差异，以及使用 5 元素块的动机是什么？我不熟悉应用这些算法的通常做法，所以也许有一些方法可以减少一些步骤，并且仍然“足够接近”中位数以确保良好的枢轴，并且这种方法更适用于 5 元素块?

我正在寻找快速排序 php 中的一些对象。

我正在对一组 OBJECTS 进行排序

我想先按 x 排序，然后是 y，然后是 z。

这是我的快速排序函数，它接受一个作业数组，并按特定的排序键（x、y 或 z 列）排序。该函数返回一个已排序的对象数组，这些对象已按排序键排序。

我可以使用快速排序递归算法轻松快速排序任何单个列，但是将它们组合在一起然后将这些子组排序到第 n 次真的让我很头疼。

有没有我可以看的算法？

基本上，我有一个名为“Employees”的容器类，其中包含一个 ArrayList。此 ArrayList 包含“Employee”对象，这些对象又包含“EmployeeData”对象，后者又包含 String 对象，例如“first”或“last”（它们是员工姓名）。

这是 ArrayList 结构的示意图：

我到底如何对 ArrayList 执行快速排序，以便其中的“Employee”对象根据字符串对象“last”按字母顺序排列？好像有点复杂！

这是我的课程的基本设计：

如您所见，这些是类。我不知道如何在“Employees”类中实现“sort”，以便通过“EmployeeData”类的“last”变量对 ArrayList 进行排序。

我刚刚花了几个小时试图在一组元素上表示快速排序算法的决策树（我还搜索了网络）。我想知道每个节点实际代表什么。是两组之间的比较（由对Partition的调用产生）吗？还是只是集合中两个元素之间的比较？我希望我的问题足够清楚。

我正在研究下面需要的程序，以便更好地理解它。

Quicksort 的最坏情况运行时间是多少，什么可能导致这种更差情况的性能？我们如何修改快速排序程序来缓解这个问题？

我知道它有最坏的情况O(n^2)，并且我知道它发生在枢轴唯一的最小或最大元素时。我的问题是如何修改程序来缓解这个问题。

一个好的算法将是好的。

我正在尝试将 heapSort 算法修改为带有 random pivot 的版本，但我不知道该怎么做。

任何人都可以帮助我吗？

这是代码：

这是使用随机 pivot 更改的代码，此代码在以下位置崩溃： Swap(ref tab[++m], ref tab[i]);

}

我有各种排序方法，它们都对相同的 100,000 个随机数数组进行排序。

我正在使用以下方法来查找每个的运行时

以下为随机数数组

我该如何修改它，以便我可以让它们中的每一个对 1​​00 个数组而不是一个数组进行排序，并计算每个数组的时间？例如。运行1 - 23ms；运行 2 - 25 毫秒；... 运行 100 - 22 毫秒

编辑： 我还有最后一件事要做。所以每次迭代都会以几种方式对数组进行排序，比如说插入、合并和快速排序。所以说插入 = 300 毫秒，合并 = 200 毫秒，快速 = 100 毫秒。对于每次迭代，我需要找到排序最快的方法。

我知道这是一个简单的最小/最大类型的事情，你在较低的编程课程中做了一千次。将每个值放入数组并使用 array.min 调用会更容易吗？（不管它实际上是什么，Java 语法的新手..）

似乎基数排序具有非常好的平均案例性能，即O(kN)：http ://en.wikipedia.org/wiki/Radix_sort

然而，似乎大多数人仍在使用快速排序——这是为什么呢？

Lomuto 分区是一种用于快速排序的简单分区算法。Lomuto 算法对子数组进行分区A[left] ... A[right]并假定A[left]为一个枢轴。如何修改此算法以A[left] ... A[right]使用给定的pivot P（不同于A[left]）进行分区？