欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序

程序员文章站 2022-05-24 08:48:45
...
/**
 * 归并排序
 * <ul>
 * <li>平均情况:O(nlog(2)n)</li>
 * <li>最好情况:O(nlog(2)n)</li>
 * <li>最坏情况:O(nlog(2)n)</li>
 * <li>辅助存储:O(n)</li>
 * <li>稳定</li>
 * <ul>
 * 
 * @timestamp Mar 12, 2016 6:29:11 PM
 * @author smallbug
 */
public class MergeSort {

	public static void main(String[] args) {
		int[] data = DataUtil.getData(100000);
		// System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		mergeSort(data);
		// System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否"));
	}

	private static void mergeSort(int[] data) {
		sort(data, 0, data.length - 1);
	}

	public static void sort(int[] data, int left, int right) {
		if (left >= right)
			return;
		// 找出中间索引
		int center = (left + right) >>> 1;
		// 对左边数组进行递归
		sort(data, left, center);
		// 对右边数组进行递归
		sort(data, center + 1, right);
		// 合并
		merge(data, left, right);
	}

	public static void merge(int[] data, int left, int right) {
		insertSort(data, left, right);
	}

	/**
	 * 局部插入排序
	 * 
	 * @timestamp Mar 12, 2016 6:28:30 PM
	 * @param data
	 * @param left
	 * @param right
	 */
	private static void insertSort(int[] data, int left, int right) {
		int temp;
		for (int i = left + 1; i <= right; i++) {
			temp = data[i];// 保存待插入的数值
			int j = i;
			for (; j > 0 && temp < data[j - 1]; j--) {
				data[j] = data[j - 1];// 如果待插入的数值前面的元素比该值大,就向后移动一位
			}
			data[j] = temp;// 插入
		}
	}
}

 

上一篇: 归并排序

下一篇: 快速排序