import java.util.Random;
public class MergeSort implements Runnable{
public void run()
{
int[] a = new int[100000];
Random p = new Random(); //产生随机数
for(int i=0;i<100000;i++)
a[i] = p.nextInt(10000);
//计时
//long startMili=System.currentTimeMillis();// 当前时间对应的毫秒数
//System.out.println("总耗时为:"+(startMili)+"毫秒");
mergeSort(a, 0, 1);
//long endMili=System.currentTimeMillis();
//System.out.println("总耗时为:"+(endMili)+"毫秒");
//System.out.println("\n总耗时为:"+(endMili-startMili)+"毫秒");
}
// private static long sum = 0;
/**
* <pre>
* 二路归并
* 原理:将两个有序表合并和一个有序表
* </pre>
*
* @param a
* @param s
* 第一个有序表的起始下标
* @param m
* 第二个有序表的起始下标
* @param t
* 第二个有序表的结束下标
*
*/
private static void merge(int[] a, int s, int m, int t) {
int[] tmp = new int[t - s + 1];
int i = s, j = m, k = 0;
while (i < m && j <= t) {
if (a[i] <= a[j]) {
tmp[k] = a[i];
k++;
i++;
} else {
tmp[k] = a[j];
// sum += (j - i) - (j - m);
j++;
k++;
}
}
while (i < m) {
tmp[k] = a[i];
i++;
k++;
}
while (j <= t) {
tmp[k] = a[j];
j++;
k++;
}
System.arraycopy(tmp, 0, a, s, tmp.length);
}
/**
*
* @param a
* @param s
* @param len
* 每次归并的有序集合的长度
*/
public static void mergeSort(int[] a, int s, int len) {
int size = a.length;
int mid = size / (len << 1);
int c = size & ((len<<1) - 1);
// -------归并到只剩一个有序集合的时候结束算法-------//
if (mid == 0)
return;
// ------进行一趟归并排序-------//
for (int i = 0; i < mid; ++i) {
s = i * 2 * len;
merge(a, s, s + len, (len << 1) + s - 1);
}
// -------将剩下的数和倒数一个有序集合归并-------//
if (c != 0)
merge(a, size - c - 2 * len, size - c, size - 1);
//
// for (int i = 0; i < a.length; ++i) {
// System.out.print(a[i] + " ");
// }
// System.out.println();
// -------递归执行下一趟归并排序------//
mergeSort(a, 0, 2 * len);
}
public static void main(String[] args) throws InterruptedException {
Thread m = new Thread(new MergeSort());
Thread m1 = new Thread(m);
Thread m2 = new Thread(m);
Thread m3 = new Thread(m);
Thread m4 = new Thread(m);
Thread m5 = new Thread(m);
//计时
long startMili1=System.currentTimeMillis();// 当前时间对应的毫秒数
System.out.println("总耗时为:"+(startMili1)+"毫秒");
m1.start();
m1.join();
long endMili1=System.currentTimeMillis();
System.out.println("总耗时为:"+(endMili1)+"毫秒");
System.out.println("总耗时为:"+(endMili1-startMili1)+"毫秒\n");
long startMili2=System.currentTimeMillis();// 当前时间对应的毫秒数
System.out.println("总耗时为:"+(startMili2)+"毫秒");
m2.start();
//m2.join();
m3.start();
//m3.join();
m4.start();
//m4.join();
m5.start();
//m5.join();
long endMili2=System.currentTimeMillis();
System.out.println("总耗时为:"+(endMili2)+"毫秒");
System.out.println("总耗时为:"+(endMili2-startMili2)+"毫秒");
}
}