结构（快速排序）-白红宇

结构（快速排序）

阅读量：6835 次

发布时间：2019-06-26

本文共 840 字，大约阅读时间需要 2 分钟。

快速排序=挖坑填数+分治法

【举例】

66 13 51 76 81 26 57 69 23

23 13 51 57 26 66 81 69 76

【Pascal版】

                         
procedure
Qsort(l,r:
longint
);
var
i,j,t:
longint
;
begin
    
i:=l;j:=r;t:=a[i];   
//在i处挖坑
    
while
i<j 
do
    
begin
        
while
(i<j)
and
(a[j]>=t) 
do
dec(j);
        
if
(i<j) 
then
begin
a[i]:=a[j]; inc(i); 
end
;  
//挖j填i
        
while
(i<j)
and
(a[i]<=t) 
do
inc(i);
        
if
(i<j) 
then
begin
a[j]:=a[i]; dec(j); 
end
;  
//挖i填j
    
end
;
    
a[i]:=t;    
//填i
    
if
l<i-
1
then
Qsort(l,i-
1
);
    
if
r<j+
1
then
Qsort(i+
1
,r);
end
;
        
      

【C++版】

                         
void
Qsort(
int
L,
int
R){ 
    
int
i=L,j=R,t=a[i];    
//在i处挖坑
    
while
(i<j){ 
        
while
(i<j && a[j]>=t)j--;
        
if
(i<j){a[i]=a[j]; i++; }  
//挖j填i
        
while
(i<j && a[i]<=t)i++;
        
if
(i<j){a[j]=a[i]; j--; }  
//挖i填j
    
}
    
a[i]=t;  
//填i
    
if
(l<i-1) Qsort(l,i-1);
    
if
(r<j+1) Qsort(i+1,r);
}
        
      