- 浏览: 206075 次
- 性别:
- 来自: 广州
文章分类
- 全部博客 (139)
- java (37)
- web (14)
- database (9)
- compute Net (1)
- design patten (4)
- 生活 (14)
- 求职 (5)
- j2me (1)
- 娱乐 (0)
- 漫画 (0)
- struts (5)
- hibernate (1)
- spring (2)
- ajax (3)
- oracle (3)
- UML&面向对象 (3)
- ffmpeg (2)
- eclipse (8)
- 技巧 (11)
- jsp (2)
- javascript (7)
- flex (2)
- xx (0)
- xxx (0)
- android (0)
- webservice (1)
- 博客 (1)
- jQuery (1)
- split (1)
- iss rewrite (1)
- 踩顶功能ajax (1)
- ext (2)
最新评论
-
longfu2012:
学习了
方法参数前加final的作用 -
irisAndKevin:
你的方法对整除有问题!
java 两数相除 四舍五入 精确 保留2位小数点、任意位小数点 -
wpf523:
...
方法参数前加final的作用 -
wpf523:
不错,解决了我的疑惑
方法参数前加final的作用 -
zhq426:
嗯,挺好用的吧
JAVASCRIPT 取得当前时间,包括农历时间 时间格式:2011年11月8日 16:54 星期二 农历辛卯年(兔) 十月十三 申时
| |||
[转贴]常用的各种排序算法的JAVA实现 [align=center]常用的各种排序算法的JAVA实现 作者:Linyco [/align] 用JAVA把《Data Structure and Algoritm Analysis in C》里面的排序算法实现了。整个结构我使用的是Strategy模式。由Sort类扮演环境角色,SortStrategy扮演抽象策略角色。具体策略角 色有六个,分别是InsertSort、BubbleSort、ChooseSort、ShellSort、MergeSort、QuickSort。分 别是插入排序、冒泡排序、选择排序、希尔排序、归并排序和快速排序。 因为代码量比较大,所以分为几次贴出,这次只贴出Sort和SortStrategy的代码。 SortStratey接口: package Utils.Sort; /** *排序算法的接口 */ interface SortStrategy { /** *利用各种算法对实现了Comparable接口的数组进行升序排列 */ public void sort(Comparable[] obj); } Sort类: package Utils.Sort; /** *排序类,通过此类的sort()可以对实现了Comparable接口的数组进行升序排序 */ public class Sort { private SortStrategy strategy; /** *构造方法,由type决定由什么算法进行排序,排序方法的单词守字母要大字,如对于快速排序应该是 uickSort *@param type 排序算法的类型 */ public Sort(String type) { try { type = "Utils.Sort." + type.trim(); Class c = Class.forName(type); strategy = (SortStrategy)c.newInstance(); } catch (Exception e) { e.printStackTrace(); } } /** *排序方法,要求待排序的数组必须实现Comparable接口 */ public void sort(Comparable[] obj) { strategy.sort(obj); }} [b]插入排序算法的JAVA实现[/b] package Utils.Sort; /** *插入排序,要求待排序的数组必须实现Comparable接口 */ public class InsertSort implements SortStrategy { /** *利用插入排序算法对obj进行排序 */ public void sort(Comparable []obj) { if (obj == null) { throw new NullPointerException("The argument can not be null!"); } /* *对数组中的第i个元素,认为它前面的i - 1个已经排序好,然后将它插入到前面的i - 1个元素中 */ int size = 1; while (size { insert(obj, size++, obj[size - 1]); } } /** *在已经排序好的数组中插入一个元素,使插入后的数组仍然有序 *@param obj 已经排序好的数组 *@param size 已经排序好的数组的大小 *@param c 待插入的元素 */ private void insert(Comparable []obj, int size, Comparable c) { for (int i = 0 ;i { if (c.compareTo(obj[i]) { System.out.println(obj[i]); //如果待插入的元素小于当前元素,则把当前元素后面的元素依次后移一位 for (int j = size ;j > i ;j-- ) { obj[j] = obj[j - 1]; } obj[i] = c; break; } } } } (待续2) 来源:[url=http://blog.csdn.net/Linyco/]http://blog.csdn.net/Linyco/[/url] [[i] 本帖最后由 铭铭 于 2005-10-13 09:01 AM 编辑 [/i]] |
| |||
快速排序算法和冒泡排序算法的JAVA实现 [b]快速排序算法的JAVA实现[/b] package Utils.Sort; /** *快速排序,要求待排序的数组必须实现Comparable接口 */ public class QuickSort implements SortStrategy { private static final int CUTOFF = 3; //当元素数大于此值时采用快速排序 /** *利用快速排序算法对数组obj进行排序,要求待排序的数组必须实现了Comparable接口 */ public void sort(Comparable[] obj) { if (obj == null) { throw new NullPointerException("The argument can not be null!"); } quickSort(obj, 0, obj.length - 1); } /** *对数组obj快速排序 *@param obj 待排序的数组 *@param left 数组的下界 *@param right 数组的上界 */ private void quickSort(Comparable[] obj, int left, int right) { if (left + CUTOFF > right) { SortStrategy ss = new ChooseSort(); ss.sort(obj); } else { //找出枢轴点,并将它放在数组最后面的位置 pivot(obj, left, right); int i = left, j = right - 1; Comparable tmp = null; while (true) { //将i, j分别移到大于/小于枢纽值的位置 //因为数组的第一个和倒数第二个元素分别小于和大于枢纽元,所以不会发生数组越界 while (obj[++i].compareTo(obj[right - 1]) {} while (obj[--j].compareTo(obj[right - 1]) > 0) {} //交换 if (i { tmp = obj[i]; obj[i] = obj[j]; obj[j] = tmp; } else break; } //将枢纽值与i指向的值交换 tmp = obj[i]; obj[i] = obj[right - 1]; obj[right - 1] = tmp; //对枢纽值左侧和右侧数组继续进行快速排序 quickSort(obj, left, i - 1); quickSort(obj, i + 1, right); } } /** *在数组obj中选取枢纽元,选取方法为取数组第一个、中间一个、最后一个元素中中间的一个。将枢纽元置于倒数第二个位置,三个中最大的放在数组最后一个位置,最小的放在第一个位置 *@param obj 要选择枢纽元的数组 *@param left 数组的下界 *@param right 数组的上界 */ private void pivot(Comparable[] obj, int left, int right) { int center = (left + right) / 2; Comparable tmp = null; if (obj[left].compareTo(obj[center]) > 0) { tmp = obj[left]; obj[left] = obj[center]; obj[center] = tmp; } if (obj[left].compareTo(obj[right]) > 0) { tmp = obj[left]; obj[left] = obj[right]; obj[right] = tmp; } if (obj[center].compareTo(obj[right]) > 0) { tmp = obj[center]; obj[center] = obj[right]; obj[center] = tmp; } //将枢纽元置于数组的倒数第二个 tmp = obj[center]; obj[center] = obj[right - 1]; obj[right - 1] = tmp; } } [b]冒泡排序算法的JAVA实现[/b] package Utils.Sort; /** *@author Linyco *利用冒泡排序法对数组排序,数组中元素必须实现了Comparable接口。 */ public class BubbleSort implements SortStrategy { /** *对数组obj中的元素以冒泡排序算法进行排序 */ public void sort(Comparable[] obj) { if (obj == null) { throw new NullPointerException("The argument can not be null!"); } Comparable tmp; for (int i = 0 ;i { //切记,每次都要从第一个开始比。最后的不用再比。 for (int j = 0 ;j { //对邻接的元素进行比较,如果后面的小,就交换 if (obj[j].compareTo(obj[j + 1]) > 0) { tmp = obj[j]; obj[j] = obj[j + 1]; obj[j + 1] = tmp; } } } } } 作者:Linyco 来源: [url=http://blog.csdn.net/Linyco/] [color=#003366]http://blog.csdn.net/Linyco/[/color] [/url] |
| |||
选择排序、归并排序和希尔排序算法的JAVA实现 [b]归并排序算法的JAVA实现[/b] package Utils.Sort; /** *归并排序,要求待排序的数组必须实现Comparable接口 */ public class MergeSort implements SortStrategy { private Comparable[] bridge; /** *利用归并排序算法对数组obj进行排序 */ public void sort(Comparable[] obj) { if (obj == null) { throw new NullPointerException("The param can not be null!"); } bridge = new Comparable[obj.length]; //初始化中间数组 mergeSort(obj, 0, obj.length - 1); //归并排序 bridge = null; } /** *将下标从left到right的数组进行归并排序 *@param obj 要排序的数组的句柄 *@param left 要排序的数组的第一个元素下标 *@param right 要排序的数组的最后一个元素的下标 */ private void mergeSort(Comparable[] obj, int left, int right) { if (left { int center = (left + right)/2; mergeSort(obj, left, center); mergeSort(obj, center + 1, right); merge(obj, left, center, right); } } /** *将两个对象数组进行归并,并使归并后为升序。归并前两个数组分别有序 *@param obj 对象数组的句柄 *@param left 左数组的第一个元素的下标 *@param center 左数组的最后一个元素的下标 *@param right 右数组的最后一个元素的下标 */ private void merge(Comparable[] obj, int left, int center, int right) { int mid = center + 1; int third = left; int tmp = left; while (left { //从两个数组中取出小的放入中间数组 if (obj[left].compareTo(obj[mid]) { bridge[third++] = obj[left++]; } else bridge[third++] = obj[mid++]; } //剩余部分依次置入中间数组 while (mid { bridge[third++] = obj[mid++]; } while (left { bridge[third++] = obj[left++]; } //将中间数组的内容拷贝回原数组 copy(obj, tmp, right); } /** *将中间数组bridge中的内容拷贝到原数组中 *@param obj 原数组的句柄 *@param left 要拷贝的第一个元素的下标 *@param right 要拷贝的最后一个元素的下标 */ private void copy(Comparable[] obj, int left, int right) { while (left { obj[left] = bridge[left]; left++; } } } [b]选择排序算法的JAVA实现[/b] package Utils.Sort; /** *@author Linyco *利用选择排序法对数组排序,数组中元素必须实现了Comparable接口。 */ public class ChooseSort implements SortStrategy { /** *对数组obj中的元素以选择排序算法进行排序 */ public void sort(Comparable[] obj) { if (obj == null) { throw new NullPointerException("The argument can not be null!"); } Comparable tmp = null; int index = 0; for (int i = 0 ;i { index = i; tmp = obj[i]; for (int j = i + 1 ;j { //对邻接的元素进行比较,如果后面的小,就记下它的位置 if (tmp.compareTo(obj[j]) > 0) { tmp = obj[j]; //要每次比较都记录下当前小的这个值! index = j; } } //将最小的元素交换到前面 tmp = obj[i]; obj[i] = obj[index]; obj[index] = tmp; } } } [b]希尔排序算法的JAVA实现[/b] package Utils.Sort; /** *希尔排序,要求待排序的数组必须实现Comparable接口 */ public class ShellSort implements SortStrategy { private int[] increment; /** *利用希尔排序算法对数组obj进行排序 */ public void sort(Comparable[] obj) { if (obj == null) { throw new NullPointerException("The argument can not be null!"); } //初始化步长 initGap(obj); //步长依次变化(递减) for (int i = increment.length - 1 ;i >= 0 ;i-- ) { int step = increment[i]; //由步长位置开始 for (int j = step ;j { Comparable tmp; //如果后面的小于前面的(相隔step),则与前面的交换 for (int m = j ;m >= step ;m = m - step ) { if (obj[m].compareTo(obj[m - step]) { tmp = obj[m - step]; obj[m - step] = obj[m]; obj[m] = tmp; } //因为之前的位置必定已经比较过,所以这里直接退出循环 else { break; } } } } } /** *根据数组的长度确定求增量的公式的最大指数,公式为pow(4, i) - 3 * pow(2, i) + 1和9 * pow(4, i) - 9 * pow(2, i) + 1 *@return int[] 两个公式的最大指数 *@param length 数组的长度 */ private int[] initExponent(int length) { int[] exp = new int[2]; exp[0] = 1; exp[1] = -1; int[] gap = new int[2]; gap[0] = gap[1] = 0; //确定两个公式的最大指数 while (gap[0] { exp[0]++; gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1); } exp[0]--; while (gap[1] { exp[1]++; gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1); } exp[1]--; return exp; } private void initGap(Comparable[] obj) { //利用公式初始化增量序列 int exp[] = initExponent(obj.length); int[] gap = new int[2]; increment = new int[exp[0] + exp[1]]; //将增量数组由大到小赋值 for (int i = exp[0] + exp[1] - 1 ;i >= 0 ;i-- ) { gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1); gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1); //将大的增量先放入增量数组,这里实际上是一个归并排序 //不需要考虑gap[0] == gap[1]的情况,因为不可能出现相等。 if (gap[0] > gap[1]) { increment[i] = gap[0]; exp[0]--; } else { increment[i] = gap[1]; exp[1]--; } } } } 作者:Linyco 来源: [url=http://blog.csdn.net/Linyco/] [color=#003366]http://blog.csdn.net/Linyco/[/color] [/url] |
发表评论
-
java 两数相除 四舍五入 精确 保留2位小数点、任意位小数点
2011-11-03 17:53 7094java 四舍五入 精确 保留2位小数点、任意位小数点 ... -
Java中对字符串进行加密和解密
2011-08-18 17:14 17021.引言在实际工作中我们常常会遇到对数据进行加密解密的工作(如 ... -
两个日期之间的天数差
2011-08-11 11:02 1578/** * 两个日期之间的天数差 * @pa ... -
java split 特殊字符 分隔数组
2011-07-28 14:48 2103public class Test { /** ... -
JAVA 取得IP地址
2011-07-21 10:32 995/** * 取得IP地址 * @param ... -
杯具博客设计
2011-07-08 22:41 836又是遇到了一个悲催的问题。 博客: 博客的设计是这样的: ... -
webservice 同步问题
2011-07-08 22:26 1025今天遇到了一个很郁闷个问题,webservice 同步问题。 ... -
二级栏目树构建
2011-05-30 15:15 773输出栏目树 public class Entr ... -
ttt
2009-10-10 12:50 736<script type="text/ ... -
JXL, POI操作excel文件zz
2009-09-27 11:59 16142008-11-10 JXL, POI操作excel文件z ... -
jxl 写 excel
2009-09-27 11:57 1000package net.blogjava.chenlb;imp ... -
方法参数前加final的作用
2009-07-17 11:01 2481方法参数前加final的作用 2009-06-28 ... -
java 调用ffmpeg执行dos bat命令 带有两个参数
2009-03-12 16:58 3403import java.io.IOException; pu ... -
java 调用ffmpeg执行dos命令
2009-03-12 16:10 1947import java.io.File; import ja ... -
增强Eclipse(MyEclipse)输入代码提示功能
2009-03-02 16:16 1600增强Eclipse(MyEclipse)输入代码提示功能 ... -
myeclipse性能提升技巧
2009-03-02 16:07 905myeclipse性能提升技巧 200 ... -
Java JDK :小心使用 boxing
2008-12-05 18:33 713[size=large]Java JDK :小心使用 boxi ... -
Java JDK:自动装箱和拆箱
2008-12-05 18:06 818[size=large]Java JDK:自动 ... -
JDK5.0新特性介绍
2008-11-16 19:13 744JDK5.0新特性介绍 [转贴 2006-02-23 15: ... -
java面向对象我基本特征
2008-11-04 15:13 749继承:子类继承父类成为特殊的父类。直接获得父类的属性和方法。是 ...
相关推荐
常用各种排序算法Java的实现_差不多了__.rar常用各种排序算法Java的实现_差不多了__.rar
十大常用排序算法(java实现),冒泡排序,简单选择排序等
关于各种排序算法的图形演示,做得很不错
用JAVA实现七个常用排序,包括:冒泡排序,插入排序,选择排序,希尔排序,快速排序,归并排序和堆排序。
用java对常用排序算法进行分析与实现.包含: 插入排序 直接插入排序、希尔排序 • 选择排序 简单选择排序、堆排序 • 交换排序 冒泡排序、快速排序 • 归并排序 • 基数排序
Java常用排序算法 Java常用排序算法 Java常用排序算法 Java常用排序算法
常见排序算法java实现,包括快速排序,归并排序,堆排序三个常用nlogn复杂度的算法
1. 一个PPT 用动画演示了 插入排序,直接插入排序,希尔排序,附带讲解。 2. 附带其他几种常用排序的java实现的源码。 3. PPT 还是简洁、美观的,可用作模板。
主要总结了常用的七大排序算法java实现!
java实现的常用的几种基本排序算法,插入、交换、选择、归并
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
Java常用8大排序算法,包含每种算法详细介绍,及代码如何实现。
java 常用排序算法 java 常用排序算法 java 常用排序算法
常用排序算法的Java实现源码,包括冒泡排序,快速排序,直接插入排序,希尔排序,直接选择排序,堆排序,归并排序,基数排序,计数排序。
用Java语言实现的几种常用的排序算法。
java 几种常用的排序算法 java 几种常用的排序算法
实现了四类排序算法,插入排序、交换排序、选择排序、归并排序,详情请看文档,其中 树形选择排序算法--选择排序、 堆排序--选择排序 这两种算法还没实现,有兴趣的自行解决
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序