c++ - 真正意义上的排序——Quicksort

Question

我们必须为自己的 Comparable 基类做一个优化的快速排序。对于我的生活，我无法让它发挥作用。该算法看起来很简单，但是我看不到让我的代码工作。我有一个 DateTime 类，它扩展了我用来测试的 Comparable 并且排序似乎有效，但是每 20 次左右就有一次运行单个值是不合适的，当我对较少的数组 block 使用插入排序时超过 8 整个排序就会乱七八糟。

在我的分区方法中，当我将枢轴移动到末尾并在开始和结束处开始我的指针 - 1 时，它会起作用。我想将枢轴移动到末尾 - 1，因为第一个和最后一个已经排序并且首先从 + 1 开始指针，然后从 -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;
}

Answer 1

根据您向我们展示的代码和您对问题所在的评论，我唯一的猜测是 from和 to并不意味着你的想法。您的代码有 to - from作为要排序的段的长度。如果这是准确的(而不仅仅是枢轴选择的近似值)那就意味着 to实际上是指向要排序的区域之外的元素。这是合理的，但是 swap<Comparable*>(*pivot, *(to))将交换列表末尾的枢轴。