- 浏览: 194504 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
hao3721:
dsfasd
ehcache 使用 -
nihaokid:
方法是不会存在在对象内存中的,它存在于方法区,建议看看jvm的 ...
Java 深层理解 父类引用指向子类对象 -
vissalan:
有一点没看明白Father f1 = (Father)s;这时 ...
Java 深层理解 父类引用指向子类对象 -
咖啡舞者:
非常感谢这种分享精神.
在BREW中实现自己的GUI(8)-IWEB的封装 -
咖啡舞者:
这是创建的代码。
在设备上调的。
界面在手机和模拟器上显示的差异
转自:http://www.blogjava.net/javacap/archive/2007/12/13/167364.html
为了便于管理,先引入个基础类:
/**
* @author yovn
*
*/
public abstract class Sorter < E extends Comparable < E >> {
public abstract void sort(E[] array, int from , int len);
public final void sort(E[] array)
{
sort(array, 0 ,array.length);
}
protected final void swap(E[] array, int from , int to)
{
E tmp = array[from];
array[from] = array[to];
array[to] = tmp;
}
}
一 插入排序
该算法在数据规模小的时候十分高效,该算法每次插入第K+1到前K个有序数组中一个合适位置,K从0开始到N-1,从而完成排序:
/**
* @author yovn
*/
public class InsertSorter < E extends Comparable < E >> extends Sorter < E > {
/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
public void sort(E[] array, int from, int len) {
E tmp = null ;
for ( int i = from + 1 ;i < from + len;i ++ )
{
tmp = array[i];
int j = i;
for (;j > from;j -- )
{
if (tmp.compareTo(array[j - 1 ]) < 0 )
{
array[j] = array[j - 1 ];
}
else break ;
}
array[j] = tmp;
}
}
}
二 冒泡排序
这可能是最简单的排序算法了,算法思想是每次从数组末端开始比较相邻两元素,把第i小的冒泡到数组的第i个位置。i从0一直到N-1从而完成排序。(当然也可以从数组开始端开始比较相邻两元素,把第i大的冒泡到数组的第N-i个位置。i从0一直到N-1从而完成排序。)
/**
* @author yovn
*
*/
public class BubbleSorter < E extends Comparable < E >> extends Sorter < E > {
private static boolean DWON = true ;
public final void bubble_down(E[] array, int from, int len)
{
for ( int i = from;i < from + len;i ++ )
{
for ( int j = from + len - 1 ;j > i;j -- )
{
if (array[j].compareTo(array[j - 1 ]) < 0 )
{
swap(array,j - 1 ,j);
}
}
}
}
public final void bubble_up(E[] array, int from, int len)
{
for ( int i = from + len - 1 ;i >= from;i -- )
{
for ( int j = from;j < i;j ++ )
{
if (array[j].compareTo(array[j + 1 ]) > 0 )
{
swap(array,j,j + 1 );
}
}
}
}
@Override
public void sort(E[] array, int from, int len) {
if (DWON)
{
bubble_down(array,from,len);
}
else
{
bubble_up(array,from,len);
}
}
}
三,选择排序
选择排序相对于冒泡来说,它不是每次发现逆序都交换,而是在找到全局第i小的时候记下该元素位置,最后跟第i个元素交换,从而保证数组最终的有序。
相对与插入排序来说,选择排序每次选出的都是全局第i小的,不会调整前i个元素了。
/**
* @author yovn
*
*/
public class SelectSorter < E extends Comparable < E >> extends Sorter < E > {
/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@Override
public void sort(E[] array, int from, int len) {
for ( int i = 0 ;i < len;i ++ )
{
int smallest = i;
int j = i + from;
for (;j < from + len;j ++ )
{
if (array[j].compareTo(array[smallest]) < 0 )
{
smallest = j;
}
}
swap(array,i,smallest);
}
}
}
四 Shell排序
Shell排序可以理解为插入排序的变种,它充分利用了插入排序的两个特点:
1)当数据规模小的时候非常高效
2)当给定数据已经有序时的时间代价为O(N)
所以,Shell排序每次把数据分成若个小块,来使用插入排序,而且之后在这若个小块排好序的情况下把它们合成大一点的小块,继续使用插入排序,不停的合并小块,知道最后成一个块,并使用插入排序。
这里每次分成若干小块是通过“增量” 来控制的,开始时增量交大,接近N/2,从而使得分割出来接近N/2个小块,逐渐的减小“增量“最终到减小到1。
一直较好的增量序列是2^k-1,2^(k-1)-1,.....7,3,1,这样可使Shell排序时间复杂度达到O(N^1.5)
所以我在实现Shell排序的时候采用该增量序列
/**
* @author yovn
*/
public class ShellSorter < E extends Comparable < E >> extends Sorter < E > {
/* (non-Javadoc)
* Our delta value choose 2^k-1,2^(k-1)-1, .7,3,1.
* complexity is O(n^1.5)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@Override
public void sort(E[] array, int from, int len) {
// 1.calculate the first delta value;
int value = 1 ;
while ((value + 1 ) * 2 < len)
{
value = (value + 1 ) * 2 - 1 ;
}
for ( int delta = value;delta >= 1 ;delta = (delta + 1 ) / 2 - 1 )
{
for ( int i = 0 ;i < delta;i ++ )
{
modify_insert_sort(array,from + i,len - i,delta);
}
}
}
private final void modify_insert_sort(E[] array, int from, int len, int delta) {
if (len <= 1 ) return ;
E tmp = null ;
for ( int i = from + delta;i < from + len;i += delta)
{
tmp = array[i];
int j = i;
for (;j > from;j -= delta)
{
if (tmp.compareTo(array[j - delta]) < 0 )
{
array[j] = array[j - delta];
}
else break ;
}
array[j] = tmp;
}
}
}
五 快速排序
快速排序是目前使用可能最广泛的排序算法了。
一般分如下步骤:
1)选择一个枢纽元素(有很对选法,我的实现里采用去中间元素的简单方法)
2)使用该枢纽元素分割数组,使得比该元素小的元素在它的左边,比它大的在右边。并把枢纽元素放在合适的位置。
3)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。
快速排序的核心在于分割算法,也可以说是最有技巧的部分。
/**
* @author yovn
*
*/
public class QuickSorter < E extends Comparable < E >> extends Sorter < E > {
/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@Override
public void sort(E[] array, int from, int len) {
q_sort(array,from,from + len - 1 );
}
private final void q_sort(E[] array, int from, int to) {
if (to - from < 1 ) return ;
int pivot = selectPivot(array,from,to);
pivot = partion(array,from,to,pivot);
q_sort(array,from,pivot - 1 );
q_sort(array,pivot + 1 ,to);
}
private int partion(E[] array, int from, int to, int pivot) {
E tmp = array[pivot];
array[pivot] = array[to]; // now to's position is available
while (from != to)
{
while (from < to && array[from].compareTo(tmp) <= 0 )from ++ ;
if (from < to)
{
array[to] = array[from]; // now from's position is available
to -- ;
}
while (from < to && array[to].compareTo(tmp) >= 0 )to -- ;
if (from < to)
{
array[from] = array[to]; // now to's position is available now
from ++ ;
}
}
array[from] = tmp;
return from;
}
private int selectPivot(E[] array, int from, int to) {
return (from + to) / 2 ;
}
}
还有归并排序,堆排序,桶式排序,基数排序,下次在归纳。
发表评论
-
Java实现通用线程池
2009-10-12 16:17 1033URL: http://blog.csdn.net/polar ... -
java 内存溢出分析
2009-10-09 15:44 1198内存溢出是指应用系统中存在无法回收的内存或使用的内存过多,最终 ... -
Java的内存泄漏
2009-10-09 13:27 801Java 的一个重要优点就 ... -
dom4j操作xml基础--Visitor访问模式解析XML
2009-07-03 17:15 1323http://www.blogjava.net/bulktre ... -
Dom4j的全面解析
2009-07-03 17:03 983作者:冰云 icecloud(AT)sin ... -
关于java使用javacomm20-win32实践总结
2009-06-21 23:34 723由于这几天要通过java调 ... -
20非常有用的Java程序片段 (下)
2009-05-26 14:29 107717. 把 Array 转换成 Map vi ... -
20非常有用的Java程序片段 (中)
2009-05-26 14:08 88112. 单实例Singleton 示例 请先阅读这篇文章 ... -
20非常有用的Java程序片段 (上)
2009-05-26 14:02 941下面是20个非常有用的Java程序片段,希望能对你有用。 1 ... -
java实现 冒泡排序 插入排序 选择排序
2009-03-16 00:47 1064package test.sort; public clas ... -
红黑树的Java实现
2009-03-16 00:42 942红黑树可能是要考虑情况最多的BST树了,它有自己的规则(见代码 ... -
排序算法复习(Java实现)(二): 归并排序,堆排序,桶式排序,基数排序
2009-03-16 00:40 1142转自:http://www.blogjava.net/java ... -
Java 深层理解 父类引用指向子类对象
2009-03-10 11:44 2637从对象的内存角度来理解试试. 假设现在有一个父类Father, ... -
java native method
2009-03-02 20:40 953一. 什么是Native Method 简单地讲,一个Na ... -
java 简介--学习笔记
2009-02-22 22:26 731一 java 特点 1 、简单 Java 设计 ... -
String理解
2009-02-21 00:44 836要理解 java中String的运作方式,必须明确一点:Str ... -
Java的时间处理
2009-02-21 00:42 8791. Java计算时间依靠1970 ...
相关推荐
三种排序算法(直接插入、冒泡、快速)的C++实现。有讲解
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
这里提供了两种常见的排序算法实现:冒泡排序和选择排序。 冒泡排序(Bubble Sort) 是一种基本的排序算法,它通过多次遍历数组,比较相邻元素的大小并交换它们,从而使最大(或最小)的元素逐渐移动到数组的最后。...
快速排序
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
算法(冒泡,选择,插入,数组排序) package Teacher; import java.io.*; import java.util.Scanner; public class Tset { public static void main(String args[]) throws IOException { // 需要排序的数组,...
java可运行排序算法:①插入排序、②冒泡排序、③选择排序、④学生学号按照成绩高低排序的一个简单实例。在java工程项目的源文件src中建立Array包,可运行这四个.java文件,便于对java中的排序算法及数组结构进一步...
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
* 冒泡排序: * 每次在无序队列里将相邻两个数一次进行比较, * 将小数调到前面,逐次比较,直至将最大的数移到 * 最后。将剩下的N-1个数继续比较,将次大数移至 * 倒数第二位。
使用java实现的4种排序算法(冒泡、快速、插入、选择),采用随机生成一个数组,然后进行排序。
Verilog/C++实现排序算法:Verilog/C++实现排序算法:冒泡排序、选择排序、并行全比较排序、串行全比较排序。
(1) 冒泡排序和快速排序; (2) 插入排序和希尔排序; (3) 选择排序和堆排序; (4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,...