《常见排序算法.doc》由会员分享，可在线阅读，更多相关《常见排序算法.doc（18页珍藏版）》请在金锄头文库上搜索。
1、常见排序算法的实现与性能比较 目录 一试验描述二试验的目的三试验的具体实现四排序算法的语言描述（java语言描述）五演示界面六. 算法效率分析（重要）七算法理论效率于实际效率对应比较（重要）一试验描述：实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法 输入：随机产生空间大小为：N = 10， 1000，10000，100000 的排序样本，取值为0,100区间 输出:1） N=10时，排序结果。 2） N=1000，10000，100000时，对同一个样本实例，不同排序完成所需的时间。 3） N=1000，10000，100000时，每个排序用不同的样本多试验几次（最低5次）得
2、出平均时间，比较不同排序算法所用的平均时间。 二试验的目的：通过对以上试验结果的分析，总结，总结对各种排序的性能分析 三试验的具体实现：本实验我采用java语言实现，编写工具为记事本（因为不需要使用到面向对象技术，主要是做排序，面向过程的，所以没有使用IDE，以求提高程序效率），使用JSE Runtime Environment1.6.0_07。源代码文件为Algorithm.java,生成的类文件为Algorithm.class.执行程序方法：使用JRE编译Algorithm.java可以执行。四排序算法的语言描述（java语言描述） 4.1 合并排序算法描述 final static in
3、t MAXVALUE = 9999999; /merge算法使用的变量 static int L; static int R; public static void Merge(int A,int p,int q,int r) /单次merge算法时候使用，提前实现 ，以便于下面多趟里面调用 int n1=q-p; int n2=r-q+1; L = new intn1+1; R = new intn2+1; for(int i = 0;i n1;i+) Li = Ap+i; for(int j = 0;j n2;j+) Rj = Aq+j; Ln1=MAXVALUE; Rn2=MAXVALU
4、E; int i = 0,j = 0; for(int k = p; k = r ;k+) if(Li=Rj) Ak = Li; i+; else Ak = Rj; j+; public static void MergeSort(int A,int p,int r) /merge排序主程序 ,递归实现，、/共3小时 int q; if(pr) q = (p+r)/2; MergeSort(A,p,q); MergeSort(A,q+1,r); Merge(A,p,q+1,r); /*-*/ 4.2 直接插入排序算法描述 public static int InsertSort(int a )
5、 /插入排序算法实现 int len =a.length; if( len= 1) return a; int temp; for(int i=1; i = 0 & ajtemp ) aj+1=aj; j-; aj+1=temp; return a; /*-*/ /希尔排序，既是改进了的插入排序4.3 希尔排序算法描述public static void ShellSort(int R,int n) int i,j,d,k;int temp;d=n/2;while(d0) for(i=d;i=0 &RjRj+d) temp=Rj; Rj=Rj+d; Rj+d=temp; j=j-d; d=d/
6、2; /*-*/4.4直接插入排序算法描述 public static void QuickSort( int R,int s,int t) /实现快速排序 哈哈 int i=s,j=t,k; int temp; if(si & Rjtemp) j-; if(ij) Ri=Rj; i+; while(ij & Ritemp) i+; if(ij) Rj=Ri; j-; Ri=temp; QuickSort(R,s,i-1); QuickSort(R,i+1,t); /*-*/ 4.5 冒泡排序算法描述public static void BubbleSort(int R,int n) /冒泡排
7、序int i,j,k; int temp; for(i=0;ii;j-) if(RjRj-1) temp=Rj; Rj=Rj-1; Rj-1=temp; 4.6 桶排序算法描述public static void BucketSort(int keys,int from,int len,int max) int temp=new intlen; int count=new intmax+1000; for(int i=0;ilen;i+) countkeysfrom+i+; / System.out.print(count+keysi+=+countkeysfrom+i+t); /calcul
8、ate position info for(int i=1;i=0;k-) keys-counttempk=tempk; 五：演示界面：1. 进入程序，会出现选择菜单：截图如下：2. 进入选择程序，我们可以安装要求输入进入相应的模块下面我们就依次安装试验要求执行每个程序模块我们来做随机样本为10的6种排序，并且输出我们做对于同一个随机样本为1000的6种排序，并且输出每种排序算法的时间耗用，以便于我们稍候分析比较各种算法效率。我们输入：1000。接着程序运行，打印出1000样本空间的6种排序算法的运行时间由于数组较小，难以分辨时间 ，所以使用了java里面的取纳秒时间方法.接着，我们做对于同一个随机样本为10000的6种排序，并且输出每种排序算法的时间耗用，以便于我们稍候分析比较各种算法效率。我们输入：10000。接着程序运行，打印出10000样本空间的6种排序算法的运行时间由于数组较小，难以分辨时间 ，所以使用了java里面的取纳秒时间方法.接着，我们做对于同一个随机样本为100000的6种排序，并且输出每种排序算法的时间耗用，以便于我们稍候分析比较各种算法效率。我们输入：100000。接着程序运行，打印出100000样本空间的6种排序算法的运行时间由于数组较大，我们输出纳秒时间同时，将其转化为了毫秒，便于阅读。3 我们开始进行这个程序主要部分：就是对6种排序，分别每种样
