分治算法策略（2）
快速排序改进算法
（1） 基本思想：
与方法 1 相比，主要做了以下改进，取无序区 R[1..H]中间的一个数 x 作为比较基准，
从左扫描找到比 x 大的数 R[i]，从右扫描找到比 x 小的数 R[j]，然后交换 R[i]和 R[j]，
直到 i>j，一趟排序结束，此时 R[1..j]的元素均小于 R[i..H]。
（2） 排序过程：
初 始 关键字 [38 65 97 49 76 13 27 49]
第一次交换后 [38 49 97 49 76 13 27 65]
第二次交换后 [38 49 27 49 76 13 97 65]
第三次交换后 [38 49 27 13 76 49 97 65]，此时 i=5，j=4，i>j
第一趟排序结束[38 49 27 13 76 49 97 65]
【示例】：
初 始 关键字 [38 65 97 49 76 13 27 49]
一趟排序之后 [38 49 27 13] [76 49 97 65]
二趟排序之后 [38 13 27] [49] [49] [76 97 65]
三趟排序之后 [13] [38 27] [49] [49] [76 65] [97]
最后的排序结果 [13] [27] [38] [49] [49] [65] [76] [97]
快速排序算法 qsort
procedure sort(l,r:longint);
var
tmp,i,j,mid:longint;
begin
i:=l;
j:=r;
mid:=a[(i+j)div 2];
repeat
{将当前序列在中间位置的数定义为中间数基准}
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
{在左半部分寻找比中间数大的数}
{在右半部分寻找比中间数小的数}
if i<=j then
begin
{若找到一组与排序目标不一致的数对则交换它们}
tmp:=a[i];a[i]:=a[j];a[j]:=tmp;
inc(i);
dec(j);
{继续找}
end;
until i>j;
{注意这里不能有等号}
if l<j then sort(l,j);
{若序列有 1 个以上的无素，则递归搜索左右区间}
资源评论
