mergesort.java

来自「包括冒泡排序」· Java 代码 · 共 77 行

package com.arithmetic;

import java.util.Random;

public class MergeSort {

	public int[] sort(int[] data) {
		int[] temp = new int[data.length];
		mergeSort(data, temp, 0, data.length - 1);
		return data;
	}

	private void mergeSort(int[] data, int[] temp, int l, int r) {
		int mid = (l + r) / 2;
		if (l == r)
			return;

		mergeSort(data, temp, l, mid);
		mergeSort(data, temp, mid + 1, r);
		for (int i = l; i <= r; i++) {
			temp[i] = data[i];
		}
		int i1 = l;
		int i2 = mid + 1;
		for (int cur = l; cur <= r; cur++) {
			if (i1 == mid + 1)
				data[cur] = temp[i2++];
			else if (i2 > r)
				data[cur] = temp[i1++];
			else if (temp[i1] < temp[i2])
				data[cur] = temp[i1++];
			else
				data[cur] = temp[i2++];
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int length = 80000;
		long time = 0, starttime = 0, endtime = 0;
		Random r = new Random();
		int[] array = new int[length];
		int n = 0;
		MergeSort mergeSort = new MergeSort();
		
		for (int i = 0; i < length; i++) {
			int x = r.nextInt();
			array[n] = x;
			n++;
		}
/*		System.out.println("排序前数组的值为：");
		for(int i=0;i<length;i++) {
			System.out.print(array[i]+",");
			if(i%1000==0) {
				System.out.println();
			}
		}*/
//		System.out.println();
		starttime = System.currentTimeMillis();
		array = mergeSort.sort(array);
		endtime = System.currentTimeMillis();
		time = endtime - starttime;
/*		System.out.println("排序后数组的值为：");
		for(int i=0;i<length;i++) {
			System.out.print(array[i]+",");
			if(i%200==0) {
				System.out.println();
			}
		}*/
//		System.out.println();
		System.out.println("所用时间为："+time);
	}

}