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]之间的数值分割为两大阵营（比参考值小的和比参考值大的）， 这里就是对前面的阵营继续进行分割。这是一个递归的过程，直到不能分割为止。

算法就简单介绍到这里啦!