排序算法的时间规模

《排序算法的时间规模》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法实验一1、实验要求(1)排序N个元素，元素是随机生成的长为1－16的字符串，n的取值为：24、26、28、210、212、214、216、218、220。算法包括：直接插入排序、冒泡排序、堆排序、归并排序、快排序。(2)排序N个元素，元素是随机生成的1－104正整数，n的取值为：24、26、28、210、212、214、216、218、220。算法包括：直接插入排序、快排序、基数排序、计数排序。2、源代码及说明源代码请参看done文件夹，说明：全局变量n为排序数目。主函数//后内容为输出函数3、数据分析数据规模排序方式468101214

2、161820insert000.0010.0040.0691.11820.797694.39513392.53radix0000.0010.0040.0160.1110.4371.676counting0000000.0160.0630.203quick0000000.0310.1881.404insert-string0000.0460.84212.776203.8453554.806bubble-string000.0150.142.32438.586merge-string00000.0160.1090.4832.262heap-st

3、ring00000.0150.1250.5612.60512.152quick-string00000.0150.0780.393.07329.39A）平方时间排序：冒泡排序：插入排序：三个图结合起来，可以看到曲线拟合相关系数颇高放大212前的数据，发现冒泡排序增长比插入排序要快，调用操作数较多。而对字符排序操作数则比对数字排序操作数要多。B）线性时间排序计数排序：基数排序：两个图结合：两种排序的数据都严格按线性增长，可以看出基数排序的操作数较多C）nlgn时间排序从图中可以看出各算法的增长速度，在同为字符串的三个排序中，归并排序和堆排序效

4、率要比快排要高。D)总览利用多点平滑函数拟合各点，再放大进行微观的分析，可以看到平方时间算法、nlgn时间算法和线性时间算法的鲜明对比。（由于是多点平滑，有些线并没有通过点）4、心得与总结本次试验加深我了对各种排序算法的工作原理、实现方式、所用的时间和空间等认识。复习了时间函数、动态分配贮存以及各种数据结构。其中最大的认识是在编程实现时，要清楚算法中各种参数的上界和下界的特殊含义，否则算法不可能正常工作，或者指针会越界出错（比如出现在partition中的p必须跑到r-1，否则不能正常工作），在以后的学习中要注意对这些细节的琢磨。