当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

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

发表于: 2013-09-28   作者:cywhoyi   来源:转载   浏览:
摘要: 如果抛开语言的限制,给你Turbo C的让你写一个排序规则,我估计很多人会开始思考空间、时间复杂度问题,想到一些列的排序算法归并、冒泡、插入、选择等基础的排序规则,但是落实到项目中,我在看公司很多员工方式都是冒泡或者采用默认的JDK自选的算法进行算法,这对于IT人士而言,如同行尸走肉,你写得每一行代码,其实都需要考虑清楚,要对你的代码负责。 在本次项目重构过程中,我看到N多冒泡排序,而且是一层套

如果抛开语言的限制,给你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);
		}
	}

}

 

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号