计算机排序算法之归并排序算法 - 黑马程序员技术交流社区

import java.util.Date;
public class Sort {
/**
* 作者：麦子
* 功能：实现归并排序排序算法
*/
public static void main(String[] args) {
int len=100000;
int[] arrg=new int[len];
for(int i=0;i<len;i++){
int t=(int)(Math.random()*100);
arrg[i]=t;
}
Merger sort7 = new Merger();
Date date12 = new Date();
long a12 = date12.getTime();
sort7.sort(arrg);
Date date13 = new Date();
long a13 = date13.getTime();
System.out.println("归并排序用时:"+(a13-a12)+"毫秒");
}
}
class Merger extends Sort{
int[][] tdarr;//由于还不知道数组长度,故先声明一个二维数组，用途为存放数组数据
//排序的方法
public void sort(int arr[])
{
int j;//j控制的是二维
tdarr = new int[arr.length][1];//方法的形参列表中引入了数组，即可实例化上面的声明的那个二维数组
for(j=0;j<arr.length;j++)
{ tdarr[j][0] = arr[j]; }
--j;
while(tdarr[0].length<arr.length)
{
if(j%2==0){
j/=2;
int m;
for(m=0;m<j;m++)
{ //将tdarr[m/2]指向归并后的数组的地址
tdarr[m] = merge(tdarr[2*m],tdarr[2*m+1],
tdarr[2*m].length,tdarr[2*m+1].length);
}
//将tdarr[m/2]指向归并后的数组的地址
tdarr[m] = tdarr[2*m];
}else{
j/=2;
j++;
for(int m=0;m<j;m++)
{ //将tdarr[m/2]指向归并后的数组的地址
tdarr[m] = merge(tdarr[2*m],tdarr[2*m+1],
tdarr[2*m].length,tdarr[2*m+1].length);
}
j--;
}
}
}
//归并两个数组的方法，此方法逻辑较为复杂,请耐心品味
public int[] merge(int arr0[],int arr1[],int x,int y){
//int x、y分别表示数组arr0、arr1的长度,为什么不直接用arr0.length、arr1.length
//是为了增强代码的可读性,以免看得云里雾里
int low0 = 0,high0 = 0,low1 = 0,high1 = 0;
//low0、high0、low1、high1分别表示的是数组arr0、arr1各自的低位指针、高位指针
int[] _arr = new int[x+y];//数组_arr用来存放归并两个子数组后的总数组
while(high0<x||high1<y){
while(high0<x&&arr0[high0]<=arr1[low1])
{ high0++; }
if(high1!=y&&high0==x)
{
for(int i=low0;i<high0;i++)
{ _arr[low1+i] = arr0[i]; }
for(int i=low1;i<y;i++)
{
high1++;
_arr[high0+i] = arr1[i];
}
}//此处即已排完
else if(high0<x)
{
for(int i=low0;i<high0;i++)
{ _arr[low1+i] = arr0[i]; }
low0 = high0;
}
while(high1<y&&arr0[low0]>=arr1[high1])
{ high1++; }
if(high0!=x&&high1==y)
{
for(int i=low1;i<high1;i++)
{ _arr[low0+i] = arr1[i]; }
for(int i=low0;i<x;i++)
{
high0++;
_arr[high1+i] = arr0[i];
}
}//此处即已排完
else if(high1<y)
{
for(int i=low1;i<high1;i++)
{ _arr[low0+i] = arr1[i]; }
low1 = high1;
}
}
return _arr;//返回归并后的数组,为什么不采用返回类型void,然后后arr0=_arr.
} //请自行了解值传递与引用传递的区别
//打印的方法
public void show()
{
for(int i=0;i<tdarr[0].length;i++)
{
System.out.print(tdarr[0][i]+" ");
}
}
}

复制代码