アルゴリズムアルゴリズム:集計ソート
またアルゴリズムを見るのに少し時間がかかりましたが、今回は集計を見ました.
統合の効率は挿入ソートよりずっと高いような気がします!
コードを渡す
テストコード
統合の効率は挿入ソートよりずっと高いような気がします!
コードを渡す
package oliver.algorithm.sort;
public class MergeSort {
public static void sort(int[] arr,int first,int last)
{
int mid=0;
if(first<last)
{
mid=(first+last)/2;
sort(arr,first,mid);
sort(arr,mid+1,last);
merge(arr,first,mid,last);
}
}
private static void merge(int [] arr,int p,int q,int r)
{
int begin1,end1,begin2,end2;
begin1=p;end1=q;
begin2=q+1;end2=r;
int []temp=new int[r-p+1];
int i=0;
while((begin1<=end1)&&(begin2<=end2))
{
if(arr[begin1]<arr[begin2])
{
temp[i]=arr[begin1];
begin1++;
}
else
{
temp[i]=arr[begin2];
begin2++;
}
i++;
}
while(begin1<=end1)
{
temp[i++]=arr[begin1++];
}
while(begin2<=end2)
{
temp[i++]=arr[begin2++];
}
for(i=0;i<=(r-p);i++)
{
arr[p+i]=temp[i];
}
}
}
テストコード
package oliver.algorithm.sort;
import java.util.Date;
public class MergeSortTest {
/**
* @param args
*/
public static void main(String[] args) {
int size=100000;
int [] arr=new int[size];
for(int i=0;i<size;i++)
{
arr[i]=size-i;
}
Long beginTime=new Date().getTime();
MergeSort.sort(arr,0,size-1);
Long endTime=new Date().getTime();
for(int a:arr)
{
System.out.print(a+" ");
}
System.out.println();
System.out.println("when n = "+size+" toke "+(endTime-beginTime)+"ms");
}
}