1、排序算法时间复杂度比较 排序算法比较主要容: 1)利用随机函数产生10000个随机整数,对这些数进行多种方法排序。 2)至少采用4种方法实现上述问题求解(可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序),并把排序后的结功能果保存在不同的文件里。 3)给出该排序算法统计每一种排序方法的性能(以运行程序所花费的时间为准进行对比),找出其中两种较快的方法。程序的主要功能:1.随机数在排序函数作用下进行排序2.程序给出随机数排序所用的时间。算法及时间复杂度(一)各个排序是算法思想:(1)直接插入排序:将一个记录插入到已排好的有序表中,从而得到一个新的,记录数增加1的有
2、序表。(2)冒泡排序:首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换,然后比较第二个记录和第三个记录的关键字。依此类推,直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序,其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序,对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。(3)快速排序:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,已达到整个序列有序。(4)选择排序:通过N-I次关键字间的比较,从N-I+1个记录中选出关键字最小
3、的记录,并和第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程序源代码:/*package test;public class SortArray private static final int Min = 1;/生成随机数最小值 private static final int Max = 10000;/生成
4、随机数最大值 private static final int Length = 10000;/生成随机数组长度(测试的朋友建议不要超过40000,不然你要等很久,如果你电脑配置绝对高的情况下你可以再加个0试试) public static void main(String args) System.out.println(数组长度:+Length+, Min:+Min+, Max:+Max); long begin; long end; int arr = getArray(Length); begin = System.currentTimeMillis(); insertSort(arr
5、.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.len
6、gth-1); end = System.currentTimeMillis(); System.out.println(快速排序法消耗时间:+(end-begin)+毫秒); begin = System.currentTimeMillis(); choiceSort(arr.clone(); end = System.currentTimeMillis(); System.out.println(选择排序法消耗时间:+(end-begin)+毫秒); /*生成随机数数组 * param length 数组长度 * return int */ private static int getAr
7、ray(int length) if(length=0)return null; int arr = new intlength; for (int i = 0; i arr.length; i+) int temp = (int)(Min+Math.random()*(Max-Min-1); arri = temp; return arr; /*快速发排序 * param arr 需要排序的数组 * param left 数组最小下标(一般是0) * param right 数组最大下标(一般是Length-1) * return int */ private static int fast
8、Sort(int arr,int left,int right) if(left right) int s = arrleft; int i = left; int j = right + 1; while(true) /向右找大于s的元素的索引 while(i+1 arr.length & arr+i -1 & arr-j s); /如果i = j 推出循环 if(i = j) break; else /教化i和j位置的元素 int t = arri; arri = arrj; arrj = t; arrleft = arrj; arrj = s; /对左面进行递归 fastSort(arr
9、,left,j-1); /对右面进行递归 fastSort(arr,j+1,right); return arr; /*插入法排序 * param arr 需要排序的数组 * return int */ private static int insertSort(int arr) for(int i = 1;i arr.length;i+) int temp = arri; int j = i - 1; while(temp arrj) arrj+1 = arrj; j-; if(j = -1) break; arrj+1 = temp; return arr; /*冒泡发排序 * param
10、 arr 需要排序的数组 * return int */ private static int bubbleSort(int arr) for(int i = 0;i arr.length;i+) /比较两个相邻的元素 for(int j = 0;j arrj+1) int t = arrj; arrj = arrj+1; arrj+1 = t; return arr; /*选择法排序 * param arr * return */ private static int choiceSort(int arr) for(int i = 0;i arr.length;i+) int m = i;
11、for(int j = i + 1;j arr.length;j+) /如果第j个元素比第m个元素小,将j赋值给m if(arrj arrm) m = j; /交换m和i两个元素的位置 if(i != m) int t = arri; arri = arrm; arrm = t; return arr; /*打印数组 * param arr 需要打印的数组 */ private static void print(int arr) if(arr=null|arr.length=0)return; for (int i = 0; i arr.length; i+) System.out.prin
12、t(arri+,); 测试结果:总结:好的算法编程技巧高效率好的程序。1、做什么都需要耐心,做设计写程序则更需要耐心。一开始的时候,好不容易写好了程序,可是等最后调试的时候发现错误很隐蔽,就很费时间了。后来我先在纸上构思出函数的功能和参数,先把各小部分编好才编主函数,考虑好接口之后才动手编,这样就比较容易成功了。2、做任何事情我决定都应该有个总体规划。之后的工作按照规划逐步展开完成。对于一个完整的程序设计,首先需要总体规划写程序的步骤,分块写,分函数写,然后写完一部分马上纠错调试。而不是像我第一次那样,一口气写完,然后再花几倍的时间调试。一步步来,走好一步再走下一步。3、感觉一开始设计结构写函数体现的是数据结构的思想,后面的调试则更加体现了人的综合素质,专业知识、坚定耐心、锲而不舍,真的缺一不可。4、通过这次实验,复习了Java语言相关知识,磨练了我的意志,是我更有了自信心。
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2