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

结合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

    震惊

    震惊

编辑推荐
原文:http://blog.csdn.net/insistgogo/article/details/7785038 1、快速排序的基本思想: 快速排
快速排序(Qucik Sort)可以说是应用最广泛的排序算法之一。它的基本思想是分治法:选择一个pivot(
两个月之前准备软考时,简单的从理论上总结了最常用的数据结构和算法,比如:线性表,链表,图。在
先说明下业务查询主要字段(id,org_code,org_name,org_count其中org_count为计算统计出的数量)按数量
冒泡排序 1、介绍: 冒泡排序和选择排序的思想是蛮力法,冒泡,顾名思义,每次选择后面一个元素(最
/* 需求:冒泡排序的实现 思路: 1,冒泡排序的基本思想是:两两比较相邻记录的关键字,如果反序则
最近工作中有这样一个场景: 一个解析器,,处理不同的音/视频文件。刚开始我选择了策略模式,照搬书
在阿里,每一位新员工进来之后都会有一位导师,导师一般都是比较资深的程序员。 我的导师是如何带我
我们在做WEB页面时,时常会选择JQuery框架的Datagrid,如Ext、EasyUI、Flexigrid,数据访问则采用Li
转至:http://blog.csdn.net/gengv/article/details/5732698 作者:gengv 终于讲到排序了,这一部分
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号