排序算法执行时间

软件121金凯1102052019算法10001000050000100000插入排序1.1ms49.9ms1387.4ms5692.6ms归并排序2.2ms103.2ms2742.2ms10630.9ms快速排序0.9ms30.5ms978.6ms5256.4ms随机化快排1.5ms28.6ms1020.0ms5230.5ms一、插入排序/***插入排序**@paramarray*/publicstaticint[]insertionSort(int[]array){inti,j;intinsertArg;//要插入的数据//从数组的第二个元素开始循环将数组中的元素插入for(i=1;iarray.length;i++){//设置数组中的第2个元素为第一次循环要播讲的数据insertArg=array[i];j=i-1;while(j=0&&insertArgarray[j]){//如果要播讲的元素小于第j个元素,就将第j个元素向后移动array[j+1]=array[j];j--;}//直到要插入的元素不小于第j个元素,将insertNote插入到数组中array[j+1]=insertArg;}//打印排序后的数组System.out.println(Arrays.toString(array));returnarray;}二、归并排序/***归并排序**@paramdata*/publicstaticint[]mergeSort(int[]arrays){sort(arrays,0,arrays.length-1);System.out.println(Arrays.toString(arrays));returnarrays;}publicstaticvoidsort(int[]data,intleft,intright){//判断左右两边的个数if(left=right)return;//找出中间索引intcenter=(left+right)/2;//对左边数组进行递归sort(data,left,center);//对右边数组进行递归sort(data,center+1,right);//合并merge(data,left,center,right);}/***将两个数组进行归并，归并前面2个数组已有序，归并后依然有序**@paramdata*数组对象*@paramleft*左数组的第一个元素的索引*@paramcenter*左数组的最后一个元素的索引，center+1是右数组第一个元素的索引*@paramright*右数组最后一个元素的索引*/publicstaticvoidmerge(int[]data,intleft,intcenter,intright){//临时数组int[]tmpArr=newint[data.length];//右数组第一个元素索引intmid=center+1;//third记录临时数组的索引intthird=left;//缓存左数组第一个元素的索引inttmp=left;while(left=center&&mid=right){//从两个数组中取出最小的放入临时数组if(data[left]=data[mid]){tmpArr[third++]=data[left++];}else{tmpArr[third++]=data[mid++];}}//剩余部分依次放入临时数组（实际上两个while只会执行其中一个）while(mid=right){tmpArr[third++]=data[mid++];}while(left=center){tmpArr[third++]=data[left++];}//将临时数组中的内容拷贝回原数组中//（原left-right范围的内容被复制回原数组）while(tmp=right){data[tmp]=tmpArr[tmp++];}}三、快速排序/***快速排序*@paramarrays*@return*/publicstaticint[]quickSort(int[]arrays){if(arrays.length0){//查看数组是否为空_quickSort(arrays,0,arrays.length-1);}System.out.println(Arrays.toString(arrays));returnarrays;}publicstaticvoid_quickSort(int[]list,intlow,inthigh){if(lowhigh){intmiddle=getMiddle(list,low,high);//将list数组进行一分为二_quickSort(list,low,middle-1);//对低字表进行递归排序_quickSort(list,middle+1,high);//对高字表进行递归排序}}privatestaticintgetMiddle(int[]src,intstart,intend){inttemp=src[start];while(startend){while(startend&&src[end]=temp){end--;}src[start]=src[end];while(startend&&src[start]=temp){start++;}src[end]=src[start];}src[start]=temp;returnstart;}四、随机化快速排序publicstaticint[]randomQuickSort(int[]arrays){if(arrays.length0){//查看数组是否为空_randomQuickSort(arrays,0,arrays.length-1);}System.out.println(Arrays.toString(arrays));returnarrays;}publicstaticvoid_randomQuickSort(int[]list,intlow,inthigh){if(lowhigh){intmiddle=getRandomMiddle(list,low,high);//将list数组进行一分为二_quickSort(list,low,middle-1);//对低字表进行递归排序_quickSort(list,middle+1,high);//对高字表进行递归排序}}privatestaticintgetRandomMiddle(int[]src,intstart,intend){Randomrandom=newRandom();intn=start+random.nextInt(end-start);inttemp=src[n];while(startend){while(startend&&src[end]=temp){end--;}src[start]=src[end];while(startend&&src[start]=temp){start++;}src[end]=src[start];}src[start]=temp;returnstart;}测试程序（模板，样例）3.1插入排序packagecom.kale.alg;importjava.util.ArrayList;publicclassTest{publicstaticvoidmain(String[]args){intnumber=100000;System.out.println(数据规模:+number);//开始生成数据ArrayListint[]list=newArrayList();int[]arrs01=fromLargeToSmall(number);//System.out.println(Arrays.toString(arrs01));int[]arrs02=fromSmallToLarge(number);list.add(arrs01);list.add(arrs02);for(inti=0;i8;i++){int[]arrsRandom=random(number);list.add(arrsRandom);}longstartTime=System.currentTimeMillis();//获取开始时间//开始排序for(inti=0;i10;i++){//取出int[]arrSort=list.get(i);//归这里根据排序的不同，设置不同的排序方法//Sort.mergeSort(arrSort);//插入排序Sort.insertionSort(arrSort);}longendTime=System.currentTimeMillis();//获取结束时间longtotalTime=endTime-startTime;System.out.println(10次排序运行时间：+totalTime+ms);System.out.println(平均物理执行时间：+(double)totalTime/10+ms);}/***产生从小到大的number个数*@paramnumber*@return*/privatestaticint[]fromSmallToLarge(intnumber){int[]arr=newint[number];for(inti=0;inumber;i++){arr[i]=i+1;}returnarr;}/***产生从大到小的number个数*@paramnumber*@return*/privatestaticint[]fromLargeToSmall(intnumber){int[]arr=newint[number];for(inti=0;inumber;i++){arr[i]=number-i+1;}returnarr;}/***产生number个随机数*@paramnumber*@return*/privatestaticint[]random(intnumber){int[]arr=newint[number];for(inti=0;inumber;i++){arr[i]=(int)(Math.random()*number);}returnarr;}}3.2归并排序packagecom.kale.alg;importjava.util.ArrayList;publicclassTest{publicstaticvoidmain(String[]args){intnumber=100000;System.out.println(数据规模:+number);//开始生成数据ArrayListint[]list=newArrayList();int[]arrs01=fromLargeToSmall(number);//System.out.println(Arrays.toString(arrs01));int[]arrs02=fromSmallToLarge(number);list.add(arrs01);list.add(arrs02);for(inti=0;i8;i++){int[]arrsRandom=random(number);list.add(arrsRandom);}longstartTime=System.currentTimeMillis();//获取开始时间//开始排序for(inti=0;i10;i++){//取出int[]arrSort=list.get(i);//归并排序Sort.mergeSort(arrSort);//插入排序//Sort.insertionSort(arrSort);}longendTime=System.currentTimeMillis();//获取结束时间longtotalTime=endTime-startTime;System.out.pri