Question

关于free pascal 的快速排序，我总解不出，求大师详解：

（主程序省略）
l 是第一个数的序号，r 是最后一个数的序号

假若输入 36 25 48 12 65 43 20 58
就请大师一步步详细解答。

Answer 1

快速排序的时间复杂度很省，是深受青睐的一种排序方式。
过程如下：
其中，第一行记录l,r以及层数（有回溯），第二行记录刚开始的赋值，第三行记录大小比较后的指向的数的位置，第四行记录交换后的指向的数，第五行是当前排序。
qsort(1,8) 1:
i=1 j=8 mid=12
i=1 a[i]=36 j=4 a[j]=12
i=2 a[i]=25 j=1 a[j]=12
12 25 48 36 65 43 20 58
qsort(2,8) 2:
i=2 j=8 mid=65
i=5 a[i]=65 j=8 a[j]=58
i=8 a[i]=65 j=7 a[j]=20
12 25 48 36 58 43 20 65
qsort(2,7) 3:
i=2 j=7 mid=36
i=3 a[i]=48 j=7 a[j]=20
i=4 a[i]=36 j=4 a[j]=36
12 25 20 36 58 43 48 65
qsort(2,3) 4:
i=2 j=3 mid=25
i=2 a[i]=25 j=3 a[j]=20
12 20 25 36 58 43 48 65
qsort(5,7) 4:
i=5 j=7 mid=43
i=5 a[i]=58 j=6 a[j]=43
12 20 25 36 43 58 48 65
qsort(6,7) 5:
i=6 j=7 mid=58
i=6 a[i]=58 j=7 a[j]=48
12 20 25 36 43 48 58 65
最后从小到大排序。

Answer 2

procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do
inc(i);
while x<a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;

如果是安装在默认目录的话C:\FPC\2.*.*\demo\text里有一个qsort.pp里有快排标程
快排就是分治，不断把比a[(l+r) div 2]大的交换到后面，小的交换到前面（从小到大排）。

Answer 3

额，这个有问题吧。。算出来的”mid“应该是a[(1+8) div 2] 即 a[9 div 2] ，在pascal中若一个数div 2若商是小数的话，就将这个数减一再div 2，即a[(9-1) div 2]=a[8 div 2]=a[4]
那么a[4]=12,求出a[i]就等于36，但是a[j]就没法求了啊，所有数都不满足，，