排序算法时间复杂度分析

算法分析与设计实验报告

姓名：龚一帆 班级：04011404 学号：2014211849 专业：计算机科学与技术

一．实验题目 二．实验目的

排序问题求解

1）以排序（分类）问题为例，掌握分治法的基本设计策略。 2）熟练掌握一般插入排序算法的实现； 3）熟练掌握快速排序算法的实现； 4) 理解常见的算法经验分析方法； 三．实验环境

计算机、C语言程序设计环境 四．实验内容与步骤 1. 生成实验数据: 代码：

intmain() {

freopen(\实验课/算法实验课/1/Data.txt\,\,stdout); srand(static_cast(time(0))); cout<<2000<

cout<

2. 实现直接插入排序算法.

思路：每个数以此往前移动，直到遇见一个数比他小，就换下一个数继续移动 代码：

voidInsertSort(int a[],int n) {

for(inti=0;i=0;j--) { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); } }

}

3. 实现快速排序算法. 思路：

使用了二分的思想，将每段数组以与该数组的第一个数比较大小的关系分类并改变它们的位置，实现这段数组总所有比第一个数大的数都在第一个数的后面，比第一个小的数都在第一个数前面，再将本次划分的两段数组再进行本次操作，直到每段数组只有一个数 代码：

voidsway(intn,int m) {

int temp=a[n]; a[n]=a[m]; a[m]=temp; }

intpartition(intp,int q) {

int n=q,s=1; while(p!=q) {

if( s&&a[n]

n=++p; }

elseif( s&&a[n]>=a[p]) {

n=--q; }

elseif( !s &&a[n]>a[q]) {

s=!s; sway(n,q);

n=--q; }

elseif( !s &&a[n]<=a[q]) {

n=++p; } } return n; }

voidqsort(intp,int q) {

int j=partition(p,q); if(p!=j) qsort(p,j-1); if(q!=j) qsort(j+1,q); }

五.实验结果与分析 测试时间： 算法 耗时 0.009696 second 插入排序 0.000980second 快速排序 分析：

插入排序的时间复杂度是O（n^2），而快速排序的时间复杂度是O（nlogn），本次数据大小为2000，理论上快排的时间大约是插入排序的百分之一，但由于IO输入输出数据等步骤的耗时，实际耗时仅为插入排序的十分之一，但效率也已经比插入排序要高许多

六.心得体会

由于之前已经研究过这两种算法，所以本次试验完成的比较顺利。算法可以说是程序的灵魂，解决同样问题的算法，会由于步骤和思路的不同导致效率大不相同，学习算法可以不断的优化我们的代码，锻炼我们的思维，改变我们的思考方式，所以我一定要好好学习算法！