pascal 快速排序

五、快速排序(由小到大)
思想：（中级本P230举例排序过程）设I为当前表头指针，J为当前表的尾指针，X为当前表的第一个元素，首先从当表前的最后J位置向前找到一个比X小的元素，此时将找到的小数放到当前表第一元素位置，I指针下移并向后找一个元素比X大的元素，此时将找到的大数放到当前表的J位置，不断按此方法循环此表，直到I等于J时退出循环，此时X的位置为I，将X放在I位置，也就是说X比表中前面数据大而比表中后面数据小，这此再用相同方法递归排序前面数据和后面数据。
参考子程序：
procedure quicksort(var a:arr;s,t:integer);
var I,j:integer;
begin
i:=s;j:=t;x:=a[s];{赋初值,确定当前表的上限s和下限t,并取区间上第一值给X}
while i begin
while (a[j]>=x) and (j>i) do j:=j-1;{J向前取值}
if j>i then begin a[i]:=a[j];i:=i+1; end;{将小的调到前}
while ( a[i]<=x) and (i if i end;
a[i]:=x;{当I=J时,找到X的位置}
if s<(i-1) then quicksort(a,s,i-1);{左区间进行递归}
if t>(i+1) then quicksort(a,i+1,t);{右区间进行递归}
end;

快速排序

快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。
快速排序被认为是当前最优秀的内部排序方法。

这个例程中假设待排序的数组是全局变量a[]。
program xxx;
var
n,i:integer;
a:array[1..10000]of integer;

procedure qsort(s,t:longint);
var
i,j,x,temp:longint;
begin
i:=s;j:=t;x:=a[(i+j)div 2];
repeat
while a[ i ]>x do inc(i); {找左边比他小的}
while a[j]if i<=j then{交换}
begin
temp:=a[ i ];a[ i ]:=a[j];a[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if sif iend;

begin
read(n);//数据个数
for i:=1 to n do read(a[i]);//读入数据
qsort(1,n);//排序
{输出}
write(a[1]);
for i:=2 to n do write(' ',a[i]);
writeln;
end.

procedure sort(l,r:integer);
var i,j,mid:integer;
begin
i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数}
repeat
while a[i]< mid do inc(i); {在左半部分寻找比中间数大的数}
while mid< a[j] do dec(j);{在右半部分寻找比中间数小的数}
if i< =j then begin {若找到一组与排序目标不一致的数对则交换它们}
swap(a[i],a[j]);
inc(i);dec(j); {继续找}
end;
until i >j;
if l< j then sort(l,j); {若未到两个数的边界，则递归搜索左右区间}
if i< r then sort(i,r);
end;{sort}

快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.

程序如下:

program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (iif iuntil i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if sif iend;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.

procedure QSort(l,r:integer);
var i,j,mid,temp:longint;
begin
i:=l; j:=r;
mid:=a[(i+j)div 2];

repeat
while a[i]>mid do inc(i);
while a[j]
if i<=j then
begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
inc(i);
dec(j);
end;

until i>j;

if iif lend;

//调试通过
//把过程中的 a 换成你要排序的 数组
//在主程序里调用
//QSort(你要排序的数的开始位置,结束位置)
//一般调用QSort(1,数组的长度)