文档介绍：算法时间复杂度
——从排序算法说起
2009-3-6星期五
排序问题
某次科研调查时得到了n个自然数,每个数均不超过1500000000(*109)。为了研究的需要,需将这n个数从大到小排序。
【输入】包含n+1行;第一行是整数n,表示自然数的个数;第2~n+1每行一个自然数。
【输出】包含n行,按照从大到小的顺序输出这n个自然数。
【限制】40%的数据满足:1<=n<=1000;80%的数据满足:1<=n<=50000;100%的数据满足:1<=n<=200000,每个数均不超过1500 000 000(*109)
思考:你将如何排序?
排序算法
冒泡排序:冒泡排序又称交换排序其基本思想是:对待排序的记录的关键字进行两两比较,如发现两个记录是反序的,则进行交换,直到无反序的记录为止。
归并排序:把数列前后各一半排好序,再把两半归并(归并的时候要花多少时间?)。拿排队情况来说……
快速排序:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束. (思考:应选怎样的数合适一些?)
归并排序和快速排序的算法区别?
算法的时间复杂度
冒泡排序:n*n?
归并排序和快速排序:n*log2n?
归并排序没有最好情况和最坏情况
快速排序会存在有好和坏的区别?期望拿来参照的数最好不要是第一个或者是最后一个?(有可能是顺序或者是倒序)
一般情况下,快速排序好于归并排序,因为代码短,并且存在最好情况,同时发生最坏的情况的概率比较低。
∴要记住qsort的代码,并在5-6分钟内敲完!
随机函数的应用
随机生成测试数据:如生成前面要求的排序的数
program ceshi;
var i,n:longint;
begin
assign(output,'');rewrite(output);
readln(n);
writeln(n);
randomize