對它的排序 - 快速排序

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))將交換樞軸關閉列表的末尾。