排序算法时间复杂度比较.docx
《排序算法时间复杂度比较.docx》由会员分享，可在线阅读，更多相关《排序算法时间复杂度比较.docx（9页珍藏版）》请在冰点文库上搜索。
排序算法时间复杂度比较
排序算法比较
主要容：
1）利用随机函数产生10000个随机整数，对这些数进行多种方法排序。
2）至少采用4种方法实现上述问题求解（可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序），并把排序后的结功能果保存在不同的文件里。
3）给出该排序算法统计每一种排序方法的性能（以运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
程序的主要功能：
1.随机数在排序函数作用下进行排序
2.程序给出随机数排序所用的时间。
算法及时间复杂度
（一）各个排序是算法思想：
（1）直接插入排序：
将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。
（2）冒泡排序：
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。
依此类推，直到第N-1和第N个记录的关键字进行过比较为止。
上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。
然后进行第二趟起泡排序，对前N-1个记录进行同样操作。
一共要进行N-1趟起泡排序。
（3）快速排序：
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。
（4）选择排序：
通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最小的记录，并和第I（1<=I<=N）个记录交换。
时间复杂度分析
排序算法
最差时间
时间复杂度
是否稳定？
插入排序
O（n2）
O（n2）
稳定
冒泡排序
O（n2）
O（n2）
稳定
快速排序
O（n2）
O（n*log2n）
不稳定
选择排序
O（n2）
O（n2）
稳定
10000个数据的时间比较：
算法名称
用时
插入排序
122
冒泡排序
343
快速排序
7
选择排序
116
程序源代码：
/**********************************************************************************************
packagetest;
publicclassSortArray{
privatestaticfinalintMin=1;//生成随机数最小值
privatestaticfinalintMax=10000;//生成随机数最大值
privatestaticfinalintLength=10000;//生成随机数组长度（测试的朋友建议不要超过40000,不然你要等很久,如果你电脑配置绝对高的情况下你可以再加个0试试）
publicstaticvoidmain（String[]args）{
System.out.println（"数组长度：
"+Length+",Min：
"+Min+",Max：
"+Max）;
longbegin;
longend;
intarr[]=getArray（Length）;
begin=System.currentTimeMillis（）;
insertSort（arr.clone（））;
end=System.currentTimeMillis（）;
System.out.println（"插入法排序法消耗时间:
"+（end-begin）+"毫秒"）;
begin=System.currentTimeMillis（）;
bubbleSort（arr.clone（））;
end=System.currentTimeMillis（）;
System.out.println（"冒泡发排序法消耗时间:
"+（end-begin）+"毫秒"）;
begin=System.currentTimeMillis（）;
fastSort（arr.clone（）,0,arr.length-1）;
end=System.currentTimeMillis（）;
System.out.println（"快速排序法消耗时间:
"+（end-begin）+"毫秒"）;
begin=System.currentTimeMillis（）;
choiceSort（arr.clone（））;
end=System.currentTimeMillis（）;
System.out.println（"选择排序法消耗时间:
"+（end-begin）+"毫秒"）;
}
/**生成随机数数组
*paramlength数组长度
*returnint[]
*/
privatestaticint[]getArray（intlength）{
if（length<=0）returnnull;
intarr[]=newint[length];
for（inti=0;iinttemp=（int）（Min+Math.random（）*（Max-Min-1））;
arr[i]=temp;
}
returnarr;
}
/**快速发排序
*paramarr需要排序的数组
*paramleft数组最小下标（一般是0）
*paramright数组最大下标（一般是Length-1）
*returnint[]
*/
privatestaticint[]fastSort（int[]arr,intleft,intright）{
if（leftints=arr[left];
inti=left;
intj=right+1;
while（true）{
//向右找大于s的元素的索引
while（i+1//向左找小于s的元素的索引
while（j-1>-1&&arr[--j]>s）;
//如果i>=j推出循环
if（i>=j）{
break;
}else{
//教化i和j位置的元素
intt=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
}
arr[left]=arr[j];
arr[j]=s;
//对左面进行递归
fastSort（arr,left,j-1）;
//对右面进行递归
fastSort（arr,j+1,right）;
}
returnarr;
}
/**插入法排序
*paramarr需要排序的数组
*returnint[]
*/
privatestaticint[]insertSort（int[]arr）{
for（inti=1;iinttemp=arr[i];
intj=i-1;
while（temparr[j+1]=arr[j];
j--;
if（j==-1）{
break;
}
}
arr[j+1]=temp;
}
returnarr;
}
/**冒泡发排序
*paramarr需要排序的数组
*returnint[]
*/
privatestaticint[]bubbleSort（int[]arr）{
for（inti=0;i//比较两个相邻的元素
for（intj=0;jif（arr[j]>arr[j+1]）{
intt=arr[j];
arr[j]=arr[j+1];
arr[j+1]=t;
}
}
}
returnarr;
}
/**选择法排序
*paramarr
*return
*/
privatestaticint[]choiceSort（int[]arr）{
for（inti=0;iintm=i;
for（intj=i+1;j//如果第j个元素比第m个元素小，将j赋值给m
if（arr[j]m=j;
}
}
//交换m和i两个元素的位置
if（i!
=m）{
intt=arr[i];
arr[i]=arr[m];
arr[m]=t;
}
}
returnarr;}
/**打印数组
*paramarr需要打印的数组
*/
privatestaticvoidprint（int[]arr）{
if（arr==null||arr.length==0）return;
for（inti=0;iSystem.out.print（arr[i]+","）;
}
}
}
测试结果：
总结：
好的算法＋编程技巧＋高效率＝好的程序。
1、做什么都需要耐心，做设计写程序则更需要耐心。
一开始的时候，好不容易写好了程序，可是等最后调试的时候发现错误很隐蔽，就很费时间了。
后来我先在纸上构思出函数的功能和参数，先把各小部分编好才编主函数,考虑好接口之后才动手编，这样就比较容易成功了。
2、做任何事情我决定都应该有个总体规划。
之后的工作按照规划逐步展开完成。
对于一个完整的程序设计，首先需要总体规划写程序的步骤，分块写,分函数写，然后写完一部分马上纠错调试。
而不是像我第一次那样，一口气写完，然后再花几倍的时间调试。
一步步来，走好一步再走下一步。
3、感觉一开始设计结构写函数体现的是数据结构的思想，后面的调试则更加体现了人的综合素质，专业知识、坚定耐心、锲而不舍，真的缺一不可。
4、通过这次实验，复习了Java语言相关知识,磨练了我的意志,是我更有了自信心。
升级会员 