标签: quicksort

以下引用来自Wikipedia Merge Sort页面中的"与其他排序算法的比较"部分

在典型的现代体系结构中,高效的快速排序实现通常优于mergesort,用于排序基于RAM的阵列.[citation needed]另一方面,合并排序是一种稳定的排序,在处理慢速访问顺序介质方面更有效.

我的问题:

1. 当要排序的数据全部适合内存时,为什么Quicksort的性能优于Mergesort？如果所需的所有数据都被缓存,或者内存中的Quicksort和Mergesort都不能快速访问？

2. 为什么Mergesort在处理缓慢访问的顺序数据方面更有效率(例如在要排序的数据不能全部适合内存的情况下从磁盘中)？

3. (从下面的评论转到此处)在arrn个元素的基元数组(数据是顺序的)中.必须在MergeSort中读取和比较的元素对是arr[0]和arr[n/2](在最终合并中发生).现在认为被读取并在快速排序相比是一对具有元件arr[1]和arr[n](在第一分区中发生时,假设我们交换与第一元件的随机选择的枢轴).我们知道数据是以块的形式读取并加载到缓存中,或者加载到磁盘到内存(如果我错了,请纠正我)那么使用MergeSort时所需的数据是否更有可能在一个块中加载？在我看来,MergeSort总是会有优势,因为它可能会比较更紧密的元素.我知道这是假的(见下图),因为QuickSort显然更快......我知道MergeSort不到位并需要额外的内存,这可能会减慢速度.除了我在分析中遗漏了哪些东西？

图像来自Princeton CS MergeSort和QuickSort幻灯片

我的动机:

我想理解上面这些概念,因为它们是为什么在排序LinkedList时首选mergeSort的主要原因之一,或者在排序数组或顺序数据时没有优先顺序数据和quickSort.为什么mergeSort用于在Java中对Object进行排序,而quickSort用于在java中对原始类型进行排序.

更新:Java 7 API实际上使用TimSort对Object进行排序,Object是MergeSort和InsertionSort的混合体.对于原语Dual-Pivot QuickSort.这些更改是从Java SE 7开始实现的.这与排序算法的稳定性有关.为什么Java的Arrays.sort方法对不同类型使用两种不同的排序算法？

编辑:

我将感谢一个解决以下方面的答案:

• 我知道两种排序算法在移动,读取和比较的数量上有所不同.如果那些原因导致了我在我的问题中列出的行为(我怀疑它),那么彻底解释排序算法的步骤和过程如何导致从磁盘或内存中寻找数据的优点或缺点将非常感激.
• 欢迎举例.我通过例子更好地学习.

注意:如果你正在阅读@ rcgldr的答案.看看我们在聊天室里的对话,它有很多很好的解释和细节.https://chat.stackoverflow.com/rooms/161554/discussion-between-rcgldr-and-oliver-koo

插入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没有就地排序,但我不确定,所以也许有人可以提供帮助.

我需要在C中编写一个排序程序,如果文件可以在适当的位置排序以节省磁盘空间,那将是很好的.数据很有价值,所以我需要确保如果进程被中断(ctrl-c),文件没有被破坏.我可以保证机器上的电源线不会被拉扯.

额外细节:文件大约40GB,记录是128位,机器是64位,操作系统是POSIX

有关实现此目的的任何提示,或一般说明？

谢谢!

澄清一下:我希望用户想要ctrl-c进程.在这种情况下,我想要优雅地退出并确保数据是安全的.所以这个问题是关于处理中断和选择一个排序算法,如果请求可以快速包装.

跟进(2年后):为了后代,我已经安装了SIGINT处理程序,它运行良好.这不能保护我免受电源故障的影响,但这是我可以处理的风险.代码位于https://code.google.com/p/pawnsbfs/source/browse/trunk/hsort.c和https://code.google.com/p/pawnsbfs/source/browse/trunk/qsort.c

我很难将QuickSort与Hoare分区转换为C代码,但无法找到原因.我正在使用的代码如下所示:

void QuickSort(int a[],int start,int end) {
    int q=HoarePartition(a,start,end);
    if (end<=start) return;
    QuickSort(a,q+1,end);
    QuickSort(a,start,q);
}

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);

        if  (i < j)
            swap(&a[i],&a[j]);
        else
            return j;
    }
}

此外,我真的不明白为什么HoarePartition工作.有人可以解释它为什么有效,或者至少把我链接到一篇文章吗？

我已经看到了分区算法的逐步完成,但我没有直观的感觉.在我的代码中,它似乎甚至没有用.例如,给定数组

13 19  9  5 12  8  7  4 11  2  6 21

它将使用数据透视表13,但最终会使用数组

 6  2  9  5 12  8  7  4 11 19 13 21 

并将返回 …

Quicksort通常被描述为原位(就地)算法,尽管它需要O(log n)堆栈空间.所以,做原地意味着"需要小于O(n)的额外空间",还是栈空间一般不能算作空间复杂度(但为什么会这样呢？),或者是快速排序实际上不是原地算法？

quicksort算法何时需要O(n ^ 2)时间？

我将为学生实现一个玩具磁带"大型机",显示"快速排序"类功能的快速性(递归与否,由于硬件速度慢,并且众所周知的堆栈反转技术并不重要) "bubblesort"函数类.因此,虽然我清楚硬件实现和控制器,但我猜测,快速排序功能在顺序,顺序和比较距离方面要比其他功能快得多(从中间回放磁带要快得多)结束,因为倒带速度不同).

不幸的是,事实并非如此; 这个简单的"气泡"代码在比较距离,方向和比较和写入次数方面与"快速排序"功能相比显示出很大的改进.

所以我有3个问题:

1. 我实施快速排序功能时是否有错？
2. 我在实现bubblesoft功能时遇到了错误吗？
3. 如果没有,为什么"bubblesort"在(比较和写入操作)中的功能比"quicksort"功能快得多？

我已经有了"quicksort"功能:

void quicksort(float *a, long l, long r, const compare_function& compare)
{
    long i=l, j=r, temp, m=(l+r)/2;
    if (l == r) return;
    if (l == r-1)
    {
        if (compare(a, l, r))
        {
            swap(a, l, r);
        }
        return;
    }
    if (l < r-1)
    {
        while (1)
        {
            i = l;
            j = r;
            while (i < m && !compare(a, i, m)) i++;
            while (m < j && !compare(a, m, j)) j--;
            if (i …

经过大量搜索c中并行快速排序的实现后,我即将潜入并自己编写代码.(我需要对一个大约100万个文本字符串的数组进行排序.)似乎我发现的所有实现都将qsort函数本身的工作分开,这在分割每个线程相对少量的工作时会产生大量的开销.

将100万个字符串除以线程数(在我的情况下是24个线程)并将它们分别放在一个节上,然后进行合并输出会不会快得多？当然,这具有理论上的缺点,即它不是就地排序,但是随着可用内存的大量存在,这不是问题.运行的机器有12个(非常快)物理/ 24逻辑核心和192 GB(是,千兆字节)的内存.目前,即使在这台机器上,排序也需要大约8分钟!

我一直在测试不同数字序列的不同排序算法的时间复杂度,直到我得到快速排序(在中间有枢轴)的结果一直是一半上升而另一半下降的序列.图:

("V"是指前半部分下降,另一部分上升的序列,"A"是指前半部分上升,另一半下降的序列.

其他类型的序列的结果看起来像我期望的那样,但是我的算法可能有问题吗？

void quicksort(int l,int p,int *tab)
{
int i=l,j=p,x=tab[(l+p)/2],w; //x - pivot
do 
{
    while (tab[i]<x)
    {
        i++;
    }
    while (x<tab[j])
    {
        j--;
    }
    if (i<=j)
    {
        w=tab[i];
        tab[i]=tab[j];
        tab[j]=w;
        i++;
        j--;
    }
}
while (i<=j);
if (l<j)
{
    quicksort(l,j,tab);
}
if (i<p)
{
    quicksort(i,p,tab);
}
}

有没有人知道是什么导致了这种奇怪的结果？

关于Quicksort(Java)的网络上的许多例子都接近于此:

private void quicksort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high-low)/2];

    while (i <= j) {

      while (numbers[i] < pivot) {
        i++;
      }

      while (numbers[j] > pivot) {
        j--;
      }

      if (i <= j) {
        exchange(i, j);
        i++;
        j--;
      }
    }

    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
}

我很困惑的是为什么有那些平等的检查:

1)while (i <= j)而不是while (i < j)

2)if (i …