快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.
例:输入一组数据小到大排序.
程序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 (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
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.
程序2:
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: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 b[i]:=b[j];i:=i+1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin b[j]:=b[i];j:=j-1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
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.
程序3（C语言）：
void quick_sort(int *array, int left, int right)
{
if(left < right)
{
int i=left,j=right; /* i,j分别为左右 游标 */
while(i != j){
/* 扫描右边查找比比基准点小的数，如果是大的只需移动下标 */
while(i!=j && array[j]>array[i]) /* 此时基准点为 array[i] */
j--;
/* 上面的循环结束，说明在右边找到一个比基准的小的数 */
if(i!=j){
array[j] = array[i] ^ array[j]; /* 将基准点从i处换到j处 */
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
i++; /* 当前下标为j的数字 已经被置换到下标为i的位置，而此时的这个数据小于基准点，所以i++为下一个左边需要比较的数 */
}
while(i!=j && array[i]<array[j]) /* 此时基准点为 array[j] */
i++;
/* 上面的循环结束，说明在左边找到一个比基准的大的数 */
if(i!=j){
array[i] = array[i] ^ array[j]; /* 将基准点从j处换到i处 */
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
j--; /* 基准点已经放到i的地方去了。下一个循环我们将比较j--处的数据是否比基准点小 */
}
};
/* 上面的循环结束，说明已经将数据安装 {小于Key的数据}Key{大约Key的数据} 排列。此时i=j指向基准点 */
quick_sort(array, left, i-1);
quick_sort(array, i+1, right);
}
}
