package com.sort.mergesort;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;
public class mergesort {
int count=0;
//比较两个数的大小若前者比后者小返回true
boolean compare(ArrayList a,int i,int j)
{
count++;
if((int)a.get(i)>(int)a.get(j))
return false;
return true;
}
//合并两个有续表
void Merge(ArrayList a,int low,int high )
{
if(low<=high)
{
int mid;
ArrayList b=new ArrayList();
if(high>low+1)
{
mid=(low+high)/2;
int i,j,k;
i=low;
j=mid+1;
k=0;
while(i<=mid&&j<=high)
{
if(i<=mid&&compare(a,i,j))
{
b.add(k,a.get(i));
k++;
i++;
}
else if(j<=high&&!compare(a,i,j))
{
b.add(k,a.get(j));
k++;
j++;
}
}
if(i<=mid)
while(i<=mid)
{
b.add(k,a.get(i));
k++;
i++;
}
if(j<=high)
while(j<=high)
{
b.add(k,a.get(j));
k++;
j++;
}
}
//如果2个数是连续的
else if(high==low+1)
{
if(compare(a,low,high))
{
b.add(a.get(low));
b.add(a.get(high));
}
else
{
b.add(a.get(high));
b.add(a.get(low));
}
}//如果剩最后一个数则不需要进行移动
else if(low==high)
{
b.add(a.get(low));
}
// a.removeAll(b);
// a.addAll(b);
for(int i=low,k=0;i<=high;i++)
{
a.set(i,b.get(k));
k++;
}
}
}
//当只剩最后两个部分时进行归并
void LastMerge(ArrayList a,int low,int partition, int high)
{
if(partition<high)
{
int i=low;
int j=partition+1;
int k=0;
ArrayList b=new ArrayList();
while(i<=partition&&j<=high)
{
if(i<=partition&&compare(a,i,j))
{
b.add(k,a.get(i));
k++;
i++;
}
else if(j<=high&&!compare(a,i,j))
{
b.add(k,a.get(j));
k++;
j++;
}
}
if(i<=partition)
while(i<=partition)
{
b.add(k,a.get(i));
k++;
i++;
}
if(j<=high)
while(j<=high)
{
b.add(k,a.get(j));
k++;
j++;
}
for( i=low,k=0;i<=high;i++)
{
a.set(i,b.get(k));
k++;
}
}
}
//计算需要归并的次数
int mergecount(int n)
{
int i=0;
while((n+1)/2!=0)
{
i++;
n/=2;
}
return i;
}
void MergeSort(ArrayList a,int n)
{
int k=1;
int total=mergecount(n);
int s=1;
while(k<total)
{
s*=2;
int i;
for(i=0;i+s<=n;i+=s)
Merge(a,i,i+s-1);
//处理剩下不足2*s的项
int p=s/2;
LastMerge(a,i,i+p-1,a.size()-1);
k++;
}
//最后一次归并时,第一部分最后一个数的索引
int p=s-1;
//做一次总的归并排序
LastMerge(a,0,p,a.size()-1);
}
//创建初始数组
void init(ArrayList arr,int num)
{
Random r=new Random(47);
for(int i=0;i<num;i++)
{
arr.add(r.nextInt(100));
}
}
//输出 结果
void printoutput(ArrayList arr)
{
Iterator it=arr.iterator();
while(it.hasNext())
System.out.println((int)it.next());
}
//构造函数
public mergesort()
{
Scanner input=new Scanner(System.in);
int num=input.nextInt();
ArrayList arr=new ArrayList(num);
init(arr,num);
MergeSort(arr,num);
printoutput(arr);
System.out.println("value of count is "+count);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
new mergesort();
}
}
评论2
最新资源