分治算法策略(2).docx_分治算法策略资源-CSDN文库

版权申诉

50 浏览量 2023-03-09 18:46:54 上传评论收藏 38KB DOCX 举报

资源推荐

资源详情

资源评论

分治算法策略（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 个以上的无素，则递归搜索左右区间}

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

内容反馈

版权申诉

G11176593

粉丝: 6917
资源: 3万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip