快速法排序(3)

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 begin

mid:=s[(first+last) div 2]; k:=(first+last) div 2; repeat

left:=first; right:=last;

while s[left]mid do dec(right); if left

z:=s[left];s[left]:=s[right];s[right]:=z; inc(left);dec(right); for i:=1 to 10 do write(s[i],' '); writeln; end;

until (right=k)or(left=k);

if firstleft+1 then qsort(left+1,last); end;

利用分治算法进行快速排序 Delphi递归快排3 1 type 2 TNTA=arrayof integer; 3 var 4 A:TNTA; 5 6 procedure QuicSort(var Arr:TNTA;AStart,AEnd:Integer); 7 var 8 I,J,Sign:integer; 9 10 procedure Switch(A,B:Integer); 11 var 12 Tmp:Integer; 13 begin 14 Tmp:=Arr[A];Arr[A]:=Arr[B];Arr[B]:=Tmp; 15 end; 16 17 begin 18 if AEnd<=AStart then Exit; 19 Sign:=(AStart+AEnd)div 2; 20 {Switch value} 21 Switch(Sign,AEnd); 22 {Start to sort}

23 J:=AStart; 24 for I := AStart to AEnd-1 do 25 begin 26 if (Arr[I]J)} then 27 begin 28 Switch(J,I); 29 Inc(J); 30 end; 31 end; 32 Switch(J,AENd); 33 QuicSort(Arr,AStart,J); 34 QuicSort(Arr,J+1,AEnd); 35 end; 36 procedure TForm1.btn1Click(Sender: TObject); 37 const 38 LEN=10000; 39 var 40 I: Integer; 41 Start:Cardinal; 42 begin 43 SetLength(A,LEN); 44 Randomize; 45 for I := Low(A) to High(A) do 46 A[I]:=Random(LEN*10); 47 Start:=GetTickCount; 48 QuicSort(A,Low(A),High(A)); 49 ShowMessageFmt('%d large quick sort take time:%d',[LEN,GetTickCount-Start]); 50 end;

Pascal，非递归快排1 1 var 2 s:packed array[0..100,1..7]of longint; 3 t:boolean; 4 i,j,k,p,l,m,n,r,x,ii,jj,o:longint; 5 a:packed array[1..200000]of longint; 6 function check:boolean; 7 begin 8 if i>2 then exit(false); 9 case i of 10 1:if s[k,3]

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 begin k:=1; t:=true; s[k,1]:=1; s[k,2]:=n; s[k,3]:=1; while k>0 do begin

r:=s[k,2];l:=s[k,1]; ii:=s[k,3];jj:=s[k,4]; if t then

if r-l>30 then begin

x:=a[(r-l+1)shr 1 +l]; ii:=s[k,1];jj:=s[k,2]; repeat

while a[ii]x do dec(jj); if ii<=jj then begin

m:=a[ii];a[ii]:=a[jj];a[jj]:=m; inc(ii);dec(jj); end; until ii>jj;

s[k,3]:=ii;s[k,4]:=jj; end else begin

for ii:=l to r do begin

m:=a[ii];jj:=ii-1;

while (m0) do begin

a[jj+1]:=a[jj]; dec(jj); end;

a[jj+1]:=m; end;

t:=false; dec(k); end; if t then

for i:=1 to 3 do

if check then break; if not t then

60 begin 61 i:=s[k,5]; 62 repeat 63 inc(i); 64 until (i>2)or check; 65 end; 66 if i>2 then begin t:=false; dec(k); end 67 else t:=true; 68 if t then 69 begin 70 s[k,5]:=i; 71 inc(k); 72 case i of 73 1:begin s[k,1]:=s[k-1,3];s[k,2]:=s[k-1,2];end; 74 2:begin s[k,1]:=s[k-1,1];s[k,2]:=s[k-1,4];end; 75 end; 76 end; 77 end; 78 end; 79 begin 80 readln(n); 81 for i:=1 to n do read(a[i]); 82 k:=1; 83 qs; 84 for i:=1 to n do //输出 85 write(a[i],' '); 86 writeln; 87 end.

经测试，非递归快排比递归快排快。 Pascal，非递归快排2 1 //此段快排使用l队列储存待处理范围 2 var 3 a:Array[1..100000] of longint; 4 l:Array[1..100000,1..2] of longint; 5 n,i:longint; 6 procedure fs;//非递归快排 7 var 8 s,e,k,j,ms,m:longint; 9 begin 10 s:=1;e:=1;l[1,1]:=1;l[1,2]:=n; 11 while s<=e do 12 begin 13 k:=l[s,1];j:=l[s,2];m:=random(j-k+1)+k; 14 ms:=a[m];a[m]:=a[k];

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

while k

while (kms) do dec(j); if k

if l[s,1]

randomize; read(n);

for i:=1 to n do read(a[i]); fs;

for i:=1 to n do write(a[i],' '); end.

//参照《数据结构》（C语言版） //调用：quicksort-->qsort-->partitions intpartitions(int a[],int low,int high){ int pivotkey=a[low]; //a[0]=a[low]; while(low

while(low=pivotkey) --high; a[low]=a[high];

while(low

//a[low]=a[0]; a[low]=pivotkey; return low; }

void qsort(int a[],int low,int high){ int pivottag; if(low

pivottag=partitions(a,low,high); qsort(a,low,pivottag-1); qsort(a,pivottag+1,high); }