TList 的 quicksort 算法研究和使用。

// 自定義的比較函數

function cmp(p1, p2: pointer): integer;

begin

end;

// quicksort原文

procedure QuickSort(SortList: PPointerList; L, R: Integer;

  SCompare: TListSortCompare);

var

  I, J: Integer;

  P, T: Pointer;

  repeat

    I := L;

    J := R;

    P := SortList^[(L + R) shr 1];

    repeat

      while SCompare(SortList^[I], P) < 0 do

        Inc(I);

      while SCompare(SortList^[J], P) > 0 do

        Dec(J);

      if I <= J then

      begin

        T := SortList^[I];

        SortList^[I] := SortList^[J];

        SortList^[J] := T;

      end;

    until I > J;

    if L < J then

      QuickSort(SortList, L, J, SCompare);

    L := I;

  until I >= R;

前幾天用到了Tlist的排序功能，可是按照幫助的說明使用後總是指針錯誤,我感到非常奇怪和惱火。于是就花了點時間了解了一下quicksort的算法和出錯的原因。

比較宏觀的講，quicksort算法就是在需要排列的數組中随機挑選一個數值作為标準，然後将其他的每個數與這個數進行比較，小的排前面，大的排後面。然後将前半部分和後半部分再進行相同的算法運算，直到不能繼續分割為止。

下面說明語句的功能:

（1）    P := SortList^[(L + R) shr 1];

   這句話的功能就是将數組中間的數取出來作為比較的參考值。因為中間值是随機的，是以參考值也是随機的。 如果将語句改成  P:=SortList^[L]; 效果一樣。

（2） while SCompare(SortList^[I], P) < 0 do

            Inc(I);

   這句話的功能就是找到比參考值大的數值。這裡需要注意了！問題就出現在這裡。

  因為是從前往後找的，正常情況下當  I = (L + R) shr 1 時，這個循環就會結束，而且永遠不會越界。但是碰巧的是我比較的是兩個浮點數，在這裡沒有等于，是以循環肯定越界。 是以大家在寫比較函數的時候一定不能忽略等于的這種情況，一定要有，否則會出錯。

（3）      while SCompare(SortList^[J], P) > 0 do

              Dec(J);

這句話功能和上面的相反，從後往前找比參考值小的，直到找到他自己就停止。

（4） if I <= J then

  這些語句就是将找到的兩個數進行交換位置了！ 這就是這個算法的精華了，一次交換解決兩個數值大小排序。

（5）  if L < J then

中間的repeat 将 [L,R]之間的數值分割為兩大陣營（比參考值小的和比參考值大的）， 這裡就是對前面的陣營繼續進行分割。這是一個遞歸的過程，直到不能分割為止。

算法就簡單介紹到這裡啦!