算法练习day3——190320（对数器、归并排序）
对数器的概念和使用
- 有一个你想要测的方法a，
- 实现一个绝对正确但是复杂度不好的方法b，
- 实现一个随机样本产生器
- 实现比对的方法
- 把方法a和方法b比对很多次来验证方法a是否正确。
- 如果有一个样本使得比对出错， 打印样本分析是哪个方法出错
- 当样本数量很多时比对测试依然正确， 可以确定方法a已经正确。
package Sort;import java.util.Arrays;public class BubbleSort {public static void main(String[] args) {int value=100;//数组中元素绝对值的最大值int size=10;//数组中元素个数的最大值boolean flag=true;for(int i=0;i<500000;i++) {int[] arr1=randomgenerator(size,value);int[] arr2=copyArray(arr1);bubbleSort(arr1);rightMethod(arr2);if(!isEqual(arr1,arr2))flag=false;break;}System.out.println(flag?"Nice":"So bad!");}public static void bubbleSort(int[] arr) {if(arr==null||arr.length<2)return;for(int end=arr.length-1;end>0;end--) {for(int i=0;iarr[i+1])swap(arr,i,i+1);}}}public static void swap(int[] arr,int i,int j) {int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}public static int[] randomgenerator(int size,int value) {//随机数生成器//Math.random()-->[0,1),double类型的//(int)((size+1)*Math.random())-->[0,size]的整型int len=(int)((size+1)*Math.random());int[] arr=new int[len];for(int i=0;i 运行结果：
2.归并排序
package Sort;public class MergeSort {public static void main(String[] args) {int[] array= {4,3,7,2,6,4,9};mergeSort(array);for(int i=0;i> 1);sortProcess(arr,L,mid);sortProcess(arr,mid+1,R);merge(arr,L,mid,R);}public static void merge(int[] arr,int L,int mid,int R) {//注意此处的R是末尾元素的位置，不是长度int[] result=new int[R-L+1];//所以此处求长度应+1int p1=L;int p2=mid+1;int i=0;while(p1<=mid&&p2<=R) {//所以此处比较应该包含mid和R，就是≤，而不是mid)while(p2<=R)result[i++]=arr[p2++];if(p2>R)while(p1<=mid)result[i++]=arr[p1++];*/while(p1<=mid) {//p1没越界，即p2越界result[i++]=arr[p1++];}while(p2<=R) {result[i++]=arr[p2++];}for(int j=0;j 算法复杂度：
使用master公式：
额外空间复杂度：，一个辅助数组的大小。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！