快速排序优质PPT.ppt

快速排序优质PPT.ppt

《快速排序优质PPT.ppt》由会员分享，可在线阅读，更多相关《快速排序优质PPT.ppt（25页珍藏版）》请在冰点文库上搜索。

对于给定的数组内的数据,如何排序?

在排序之前,先设定一个哨兵值,一般选择a0,将其值赋给一个临时变量:

temp=a0;

与合并排序类似，合并排序为平分数据序列，而快速排序通过确定第一个元素在数组中的位置将序列分为左右两部分。

然后开始左右移动下标i、j值，直到（ai=temp且aj=temp）或（i=j）停止.,i,j,temp,45,快速排序:

当ai=temp，aj=temp两个条件同时满足时，交换ai、aj的值,i,j,temp,45,快速排序:

交换完后，继续开始左右移动下标i、j值，直到（ai=temp且aj=temp）或（i=j）停止.,i,j,temp,45,快速排序:

这时45的位置在数组中就已经确定了，接下来我们只需要对04数组元素以及69数组元素两部分进行排序即可，原理同上。

例如：

确定45在数组中的位置如何编程实现？

intqSort_pos（inta,intlow,inthigh）inttemp=alow,i=low,j=high,tmp;

while（i=temp）,voidswap（int*a,int*b）inttemp;

temp=*a;

*a=*b;

*b=temp;

voidqSort（inta,intlow,inthigh）intpos;

if（lowhigh）pos=qSort_pos（a,low,high）;

qSort（a,low,pos-1）;

qSort（a,pos+1,high）;

递归代码，与合并排序类似,快速排序算法：

状态:

Accepted测评机：

Xeond6得分：

100分提交日期：

2010-10-2423:

02:

00有效耗时：

1031毫秒测试结果1:

通过本测试点|有效耗时47ms测试结果2:

通过本测试点|有效耗时47ms测试结果3:

通过本测试点|有效耗时46ms测试结果4:

通过本测试点|有效耗时63ms测试结果5:

通过本测试点|有效耗时94ms测试结果6:

通过本测试点|有效耗时125ms测试结果7:

通过本测试点|有效耗时109ms测试结果8:

通过本测试点|有效耗时219ms测试结果9:

通过本测试点|有效耗时234ms测试结果10:

通过本测试点|有效耗时47ms,合并排序算法：

Xeost5得分：

2010-10-2013:

24:

3297毫秒测试结果1:

通过本测试点|有效耗时62ms测试结果2:

通过本测试点|有效耗时63ms测试结果4:

通过本测试点|有效耗时94ms测试结果5:

通过本测试点|有效耗时312ms测试结果6:

通过本测试点|有效耗时453ms测试结果7:

通过本测试点|有效耗时344ms测试结果8:

通过本测试点|有效耗时922ms测试结果9:

通过本测试点|有效耗时938ms测试结果10:

通过本测试点|有效耗时62ms,统计数字测试时间,