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