标签: quicksort

我一直在网上寻找一段时间,我想知道是否存在通常使用的快速排序的"稳定"事实实现？我可以写自己的,但为什么重新发明轮子......

我有一个我在这里写的快速入口:

void swap(int& a, int& b);
int mid(int lo, int hi);

// My quicksort implementation
void sort(int vec[], int lo, int hi)
{
        int mid;
        if (hi > lo) {
                int i = lo + 1;
                int j = hi;
                int p = mid(lo, hi);
                swap(vec[lo], vec[p]);
                mid = vec[lo];
                while (i < j) {
                        if (vec[i] <= mid) {
                                i++;
                        } else {
                                while (i < --j && vec[j] >= mid);
                                swap(vec[i], vec[j]);
                        }
                }
                i++;
                swap(vec[lo], vec[i]);
                sort(vec, …

我发现了一种方法可以改进(就我已经测试过的)快速排序算法,超出了已经完成的范围.我正在测试它,然后我想了解它.但是,我会感谢一些帮助.所以这是我的问题.顺便说一句,我的所有代码都是用C++编写的.

1. 我一直在与我的快速排序进行比较的一种方法是来自C++标准库的std :: sort.但是,它似乎非常缓慢.我只是排序整数和长期数组,但它似乎比我的快速排序和Bentley和McIlroy(也许是Sedgewick)的标准快速排序慢了大约8-10倍.有没有人有任何想法,为什么它这么慢？我用于排序的代码只是std :: sort(a,a + numelem); 其中a是long或int的数组,numelem是数组中元素的数量.数字是非常随机的,我尝试了不同的大小以及不同数量的重复元素.我也尝试过qsort,但是我的预期更糟糕了.编辑:忽略第一个问题 - 它已经解决了.

2. 我想找到更好的quicksort实现来与我的quicksort进行比较.到目前为止,我有一个Bentley-McIlroy,我还与Vladimir Yaroslavskiy的双枢轴快速排序的第一个版本进行了比较.另外,我计划移植timsort(我认为这是合并类型)和来自jdk 7源的优化双枢轴快速排序.你知道其他什么样的快速实施方案？如果他们不是C或C++,那可能没事,因为我非常擅长移植,但如果你知道它们我会更喜欢C或C++.

3. 你会如何推荐关于我对quicksort的补充？到目前为止,我的quicksort似乎比我测试过的所有其他quicksort快得多.它速度的主要来源是它比我发现的其他方法更有效地处理重复元素.它几乎完全消除了最坏情况的行为,而没有在检查重复元素上花费太多时间.我在Java论坛上发布了它,但没有得到回复.我还试着写信给Jon Bentley,因为他正在与弗拉基米尔合作进行他的双枢轴快速反应并没有得到任何回应(尽管我对此并不感到非常惊讶).我应该写一篇关于它的论文并把它放在arxiv上.ORG？我应该在一些论坛上发帖吗？我应该发布一些邮件列表吗？我已经在这方面工作了一段时间,我的方法是合法的.我确实有一些出版研究的经验,因为我是计算物理学的博士候选人.我应该尝试接触我大学计算机科学系的某个人吗？顺便说一句,我还开发了一个不同的双枢轴快速排序,但它并不比我的单枢轴快速排序更好(尽管它比弗拉基米尔的双枢轴快速排序更好,有一些数据集).

我非常感谢你的帮助.我只想将我能为计算机世界添加的内容.我对这种或任何荒谬的事情申请专利并不感兴趣.

我最近在C#中实现了QuickSort算法.对包含数百万个项目的整数数组进行排序,代码的性能比.NET的实现大约低10%.

private static void QS(int[] arr, int left, int right)
{
    if (left >= right) return;

    var pIndex = Partition(arr, left, right);
    QS( arr, left, pIndex);
    QS( arr, pIndex + 1, right);
}

在包含500万个项目的数组中,此代码比.NET慢大约60ms.

随后,我创建了另一个方法,该Partition()方法具有内联方法QS()(消除方法调用和return语句).然而,这导致性能下降到比.NET的排序方法慢约250ms.

为什么会这样？

编辑:这是该Partition()方法的代码.在内联版本中QS(),除了return语句之外,此方法的全部内容都替换了该var pIndex = Partition(arr, left, right);行.

private static int Partition(int[] arr, int left, int right)
{
    int pivot = arr[left];
    int leftPoint = left - 1;
    int pIndex = …

我知道quicksort的O(n log n)平均时间复杂度.伪快速排序(当你从足够远的地方看它,具有适当高的抽象级别时只是一个快速排序),通常用于演示函数语言的简洁性如下(在Haskell中给出):

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]

好的,所以我知道这件事有问题.最大的问题是它没有排序,这通常是quicksort的一大优势.即使这没关系,它仍然需要比典型的快速排序更长的时间,因为它在分区时必须进行两次列表传递,然后它会进行昂贵的附加操作以将其拼接回来.此外,选择第一个元素作为枢轴不是最佳选择.

但即便考虑所有这些,这个快速排序的平均时间复杂度与标准快速排序不同吗？即,O(n log n)？因为追加和分区仍然具有线性时间复杂度,即使它们效率低下.

在算法简介中, p169它讨论了使用尾递归Quicksort.

本章前面的原始Quicksort算法是(伪代码)

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

使用尾递归的优化版本如下

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

在哪里Partition根据枢轴对阵列进行排序.

不同之处在于第二种算法只调用Quicksort一次来对LHS进行排序.

有人可以向我解释为什么第一个算法可能导致堆栈溢出,而第二个算法不会？或者我误解了这本书.

我正在编写一个程序,它将读取包含5,163个名称的文本文件.(文字文件可以在这里看到)

然后我想将名称存储到名为"names"的列表中,之后,我根据名称包含的字母数量对列表进行排序,较短的名称位于列表的开头,较长的名称位于结尾.

我使用quicksort对列表进行排序,但是当我运行它时,它会显示以下错误:

C:\Python27\python.exe C:/Users/Lenovo/Desktop/Anagrams/Main.py
Traceback (most recent call last):
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 25, in <module>
    names = quicksort(names)
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
    lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
    greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
  File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
    lesser = quicksort([x …

我实施了3次QuickSort算法并测量了5000万随机数的排序时间:

1. 顺序(花了~14秒)

2. 与Parallel.Invoke()在相同的方法作为排序算法(使用了〜12秒)

3. 与Parallel.Invoke()在单独的方法(使用了约7秒)的

所以我的问题是:Parallel.Invoke()如果呼叫是在一个单独的方法中,为什么会快得多？在我的计算机上,3.示例的速度是2的两倍多.

2. Parallel.Invoke()在相同的方法作为排序算法

public class ParallelQuickSort
{

    private const int Threshold = 100;

    public static void Sort(int[] array)
    {
        if (array == null || array.Length == 0)
        {
            new ArgumentException("number array must be at least of length 1");
        }
        QuickSort(array, 0, array.Length - 1);
    }

    private static void QuickSort(int[] array, int left, int right)
    {
        var i = left;
        var j = right; …

我有这个看似琐碎的并行快速实现,代码如下:

import System.Random
import Control.Parallel
import Data.List

quicksort :: Ord a => [a] -> [a]
quicksort xs = pQuicksort 16 xs -- 16 is the number of sparks used to sort

-- pQuicksort, parallelQuicksort  
-- As long as n > 0 evaluates the lower and upper part of the list in parallel,
-- when we have recursed deep enough, n==0, this turns into a serial quicksort.
pQuicksort :: Ord a => Int -> [a] -> [a]
pQuicksort _ [] = …

根据这里的算法,看看我在"X"的情况,发生以下情况:

场景: i - >"X","X">"P"

1. swap("X", "Z"), gt--;   // the value at i is now "Z", which is still > "P"
2. swap("Z", "Y"), gt--;   // the value at i is now "Y", which is still > "P"
3. swap("Y", "C"), gt--;    // Now we finally get a value at i "C" which is < "P"
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

为什么我们不直接递减gt,直到gt指向<lt的值(在这种情况下为"P"),然后我们将此值与i处的值交换.这将节省交换操作.

因此,如果我们为上述场景做到这一点,我们将做:

1. gt--
2. …