结合Comparable接口优化排序，给新员工

如果抛开语言的限制，给你Turbo C的让你写一个排序规则，我估计很多人会开始思考空间、时间复杂度问题，想到一些列的排序算法归并、冒泡、插入、选择等基础的排序规则，但是落实到项目中，我在看公司很多员工方式都是冒泡或者采用默认的JDK自选的算法进行算法，这对于IT人士而言，如同行尸走肉，你写得每一行代码，其实都需要考虑清楚，要对你的代码负责。

在本次项目重构过程中，我看到N多冒泡排序，而且是一层套一层，N^n这代码如果数据量一旦非常大，你会发现很难发现问题存在性，你不可能实时查看CPU、Memory，还是希望能够对于自身代码的负责。

 代码非常简单，主要是提醒大家能够在写代码时候，时时刻刻谨记。

 

package org.dxy.util;

import java.lang.reflect.Array;

public class MergeSort {

	public static void main(String[] args) {
		Integer[] array = new Integer[] { 11111, 24, 90, 234, 15, 478, 12, 55,
				901, 213, 56, 11, 23, 4, 5, 67, 113, 34 };
		sort(array);
		for (Integer val : array) {
			System.out.println(val);
		}
	}

	@SuppressWarnings("unchecked")
	public static <T extends Comparable<? super T>> void sort(T[] a) {
		T[] helper = (T[]) Array.newInstance(a[0].getClass(), a.length);
		mergesort(a, helper, 0, a.length - 1);
	}

	private static <T extends Comparable<? super T>> void mergesort(T[] a,
			T[] helper, int lo, int hi) {
		if (lo >= hi)
			return;
		int mid = lo + (hi - lo) / 2;
		mergesort(a, helper, lo, mid);
		mergesort(a, helper, mid + 1, hi);
		merge(a, helper, lo, mid, hi);
	}

	private static <T extends Comparable<? super T>> void merge(T[] a,
			T[] helper, int lo, int mid, int hi) {
		for (int i = lo; i <= hi; i++) {
			helper[i] = a[i];
		}
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			// 左边的超出范围，就选择右边
			if (i > mid) {
				System.out.println("i :" + i + " mid :" + mid);
				a[k] = helper[j++];
			}
			// 右边超出范围，选择左边
			else if (j > hi) {
				System.out.println("j :" + j + " hi :" + hi);
				a[k] = helper[i++];
			} else if (isLess(helper[i], helper[j])) {
				a[k] = helper[i++];
			} else {
				a[k] = helper[j++];
			}
		}
	}

	private static <T extends Comparable<? super T>> boolean isLess(T a, T b) {
		//可以采用模板的方式，子类重写改方法，进行比较
		return a.compareTo(b) < 0;
	}
}

 

如果使用Java Fork/Join pool

package org.dxy.util;

import java.lang.reflect.Array;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

class MergeSortTask<T extends Comparable<? super T>> extends RecursiveAction {
	private static final long serialVersionUID = -749935388568367268L;
	private final T[] a;
	private final T[] helper;
	private final int lo;
	private final int hi;

	public MergeSortTask(T[] a, T[] helper, int lo, int hi) {
		this.a = a;
		this.helper = helper;
		this.lo = lo;
		this.hi = hi;
	}

	@Override
	protected void compute() {
		if (lo >= hi)
			return;
		int mid = lo + (hi - lo) / 2;
		MergeSortTask<T> left = new MergeSortTask<T>(a, helper, lo, mid);
		MergeSortTask<T> right = new MergeSortTask<T>(a, helper, mid + 1, hi);
		invokeAll(left, right);
		merge(this.a, this.helper, this.lo, mid, this.hi);

	}

	private void merge(T[] a, T[] helper, int lo, int mid, int hi) {
		for (int i = lo; i <= hi; i++) {
			helper[i] = a[i];
		}
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid) {
				a[k] = helper[j++];
			} else if (j > hi) {
				a[k] = helper[i++];
			} else if (isLess(helper[i], helper[j])) {
				a[k] = helper[i++];
			} else {
				a[k] = helper[j++];
			}
		}
	}

	private boolean isLess(T a, T b) {
		return a.compareTo(b) < 0;
	}

	@SuppressWarnings("unchecked")
	public static <T extends Comparable<? super T>> void sort(T[] a) {
		T[] helper = (T[]) Array.newInstance(a[0].getClass(), a.length);
		ForkJoinPool forkJoinPool = new ForkJoinPool(10);
		forkJoinPool.invoke(new MergeSortTask<T>(a, helper, 0, a.length - 1));
	}

	public static void main(String[] args) {
		Integer[] array = new Integer[] { 1, 24, 90, 234, 15, 478, 12, 55,
				901, 213, 56, 11, 23, 4, 5, 67, 113, 34 };
		sort(array);
		for (Integer val : array) {
			System.out.println(val);
		}
	}

}

 

评论

2 楼 cywhoyi 2013-11-04  

li15038043160_ 写道

JDK自带Arrays.sort()好像是快速排序哦，比归并排序还好一点点，因为不用双倍空间！

谢谢提醒，主要是看到公司代码中冒泡到处都是，让人无语。

1 楼 li15038043160_ 2013-11-04  

JDK自带Arrays.sort()好像是快速排序哦，比归并排序还好一点点，因为不用双倍空间！