java 实现合并排序
package How; import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.lang.reflect.Array;
import java.util.Random; import org.omg.PortableInterceptor.DISCARDING; public class bin_1
{
public static void main(String[] args)
{
try
{
mergesortSort myMergesortSort=new mergesortSort();
myMergesortSort.display();
} catch (IOException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
class mergesortSort
{
int size=6;
int []array;
int []temp;
BufferedWriter fout_1;
BufferedWriter fout_2;
//准备数据
public mergesortSort() throws IOException
{
fout_1=new BufferedWriter(new FileWriter("noOrder.txt"));
fout_2=new BufferedWriter(new FileWriter("inOrder.txt"));
Random random=new Random();
array=new int[size];
this.temp=new int[size];
for(int i=0; i<size; i++)
{
array[i]=random.nextInt(100);
fout_1.write(array[i]+"");
fout_1.newLine();
}
fout_1.flush();
mergesort( 0, size-1);
}
//方便调用
public mergesortSort(int []array, int l, int r ) throws IOException
{
fout_1=new BufferedWriter(new FileWriter("noOrder.txt"));
fout_2=new BufferedWriter(new FileWriter("inOrder.txt"));
this.array=array;
this.temp=new int[l-r+1];
mergesort( l, r);
}
public mergesortSort(int []array) throws IOException
{
fout_1=new BufferedWriter(new FileWriter("noOrder.txt"));
fout_2=new BufferedWriter(new FileWriter("inOrder.txt"));
this.array=array;
this.temp=new int[array.length];
mergesort( 0, array.length-1);
}
public void mergesort(int l, int r)
{
if(l<r)
{
int m=(l+r)/2;
mergesort( l, m);
mergesort( m+1, r);
merge( l, m, r);
}
}
public void merge(int l, int m, int r)
{
int p=l;
int q=m+1;
int k=0;
System.out.println("p="+p);
System.out.println("q="+q);
while(p<=m&&r>=q)
{
if(array[p]<=array[q]) //谁小谁先进
{
temp[k++]=array[p];
p++;
}
else
{
temp[k++]=array[q];
q++;
}
System.out.println(""+array[k]);
}
if(p<=m)
{
for(int i=p; i<=m; i++)
{
temp[k++]=array[i];
}
}
else
{
for(int i=q; i<=r; i++)
{
temp[k++]=array[i];
}
}
//复制 这里比较容易出错
for(int i=0; i<k; i++)
{
array[l++]=temp[i];
}
}
public void display() throws IOException
{ for(int i=0; i<array.length; i++)
{
fout_2.write(""+array[i]);
fout_2.newLine();
}
fout_2.flush();
}
}
运行结果