无意义排序--快速排序

Question

我们需要为自己的Comparable基类编写优化后的快速排序。我无论如何都无法使其正常工作。算法似乎很直观，但是我无法让我的代码正常工作。我有一个扩展了Comparable的DateTime类用于测试排序，排序似乎可以工作，但大约每20次运行中就会有一个值位置不正确，并且当我在小于8的数组块上使用插入排序时，整个排序就会被搞砸。

在我的partition方法中，当我将枢轴移到末尾并从开头和结尾-1开始我的指针时，它有点起作用。我想将枢轴移动到end-1，因为第一个和最后一个已经排序好，并且以first + 1和end-2开始指针，但是如果我尝试这样做，一切都会崩溃，我不明白为什么。

所以现在我有了一些可行的东西。如果我不在较小的子数组上使用插入排序，它会变得有点混乱，这使我很困扰，但我最终会弄清楚的。感谢ben j指出关于掉出数组的问题...那导致了插入排序的问题。 :)

我的当前代码如下

    Comparable** partition(Comparable** from, Comparable** to)
{
    Comparable** pivot  = from + (to - from) / 2;
    SortFirstMiddleLast(from, pivot, to - 1);
    swap(*pivot, *to);
    pivot = to;
    ++from; to -= 2;
    while (from <= to)
    {
        while (**from <= **pivot && from <= to) ++from;
        while (**to   >= **pivot && from <= to) --to;
        if (from < to)
        {
            swap(*from, *to);
            ++from; --to;
        }
    }
    swap(*from, *pivot);
    return from;
}

- Falko

---

顺便提一下，对于swap函数，你并不需要使用<Comparable*>...它会自动推断。 :) - user541686

我的做法是先让它能够处理整型，然后再修改使其可以处理其他类型。 - user2100815

Answer 1

从您展示的代码和对出错原因的评论来看，我唯一的猜测是您对“from”和“to”的理解可能有误。您的代码将“to-from”作为要排序的段的长度。如果这是准确的（而不仅仅是用于选择枢轴的近似值），那么这意味着“to”实际上指向了要排序区域的末尾元素的下一个位置。这是合理的，但是swap<Comparable*>(*pivot, *(to))会将枢轴与列表末尾交换。

- Ben Jackson

---

我在函数调用中调整了指针，以解决偏移一个的问题...我可能应该在我的帖子中包含这个...有没有一种方法可以在快速排序函数中修复它，而不会在后续递归调用中丢失索引？ - Falko