对它的排序 - 快速排序

Question

我们必须为自己的可比较的基类做一个优化的快速排序。对于我的生活，我不能让它工作。该算法看起来很简单，但我看不出让我的代码工作。我有一个扩展Comparable的DateTime类，用于测试，并且排序似乎有效，但每20个左右运行一个单独的值是不合适的，当我在数组块上使用插入排序总数超过8个，全部都会被击晕。

在我的分区方法中，当我将枢轴移动到末尾并在开始和结束时开始我的指针时，这种方式有效 - 1.我想将枢轴移动到结尾-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))将交换枢轴关闭列表的末尾。