- 浏览: 257901 次
- 性别:
- 来自: 苏州
文章分类
- 全部博客 (289)
- java (72)
- oracle (3)
- mysql (5)
- spring (28)
- hibernate (2)
- osgi (0)
- linux (2)
- ExtJs (1)
- jvm (0)
- mybatis (7)
- 分布式 (11)
- MINA (6)
- apache+tomcat (13)
- js+htm (7)
- android (44)
- http (1)
- hbase+hdoop (0)
- memcache (13)
- search (27)
- 部署及性能 (12)
- mongoDB (2)
- 多线程 (12)
- 安全管理验证 (9)
- struts (1)
- webservice (0)
- easyUI (1)
- spring security (16)
- pattern (6)
- 算法 (2)
最新评论
-
lzh8189146:
CommonsHttpSolrServer这个类,现在是不是没 ...
CommonsHttpSolrServer -
xiaochanzi:
我按照你的方法试了下,tomcat6可以发布,但是访问任何网页 ...
基于内嵌Tomcat的应用开发 -
phoneeye:
麻烦你,如果是抄来的文章,请给出来源。谢谢
ant 两则技巧 -
neverforget:
转载不注明出处
Spring Security3.1登陆验证 替换 usernamepasswordfilter -
liang1022:
若不使用eclipse ,如何在命令行下 运行服务端程序 ?
WebService CXF学习(入门篇2):HelloWorld
为了便于管理,先引入个基础类:
/**
* @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 keytool 安全证书学习笔记
2012-08-02 14:16 793http://linliangyi2007.iteye.com ... -
java国际化
2012-07-16 14:08 407http://lavasoft.blog.51cto.com/ ... -
Java版远程控制V1.0
2012-06-17 21:37 746http://www.cnblogs.com/syxchina ... -
浅析Java中CountDownLatch用法
2012-05-16 20:57 791CountDownLatch如其所写,是一个 ... -
SMTP发送邮件
2012-04-18 09:41 752SMTP发送邮件 openkk 2011-06-0 ... -
smtp 返回代码 信息
2012-04-18 08:52 1440SMTP Server Response Cod ... -
JavaMail详解
2012-04-18 02:24 0JavaMail详解 博客分类: JAV ... -
安装Eclipse反编译插件
2012-04-17 09:34 797安装Eclipse反编译插件 博客分类: ... -
Java编程中“为了性能”尽量要做到的一些地方
2012-04-13 08:30 658最近的机器内存又爆满了,除了新增机器内存外,还应该好好r ... -
Dijkstra算法
2012-04-11 08:00 859Dijkstra算法 博客分类: 算 ... -
java 播放音乐
2012-04-11 08:00 992java 播放音乐 博客分类: J2 ... -
Java中的native,transient,volatile和strictfp关键字
2012-04-06 08:49 724Java中的native,transient,v ... -
用ReentrantLock模拟宴会的热闹情景
2012-04-05 08:32 897用ReentrantLock模拟宴会的热闹情景 ... -
Hashmap 分析
2012-04-05 08:32 723Hashmap 博客分类: 算法 ... -
ExecutorService线程池
2012-04-05 08:32 751ExecutorService线程池 (2010 ... -
Java并发:juc Executor框架详解
2012-04-05 08:32 773Java并发:juc Executor ... -
java并发包,多线程,工具类,笔记
2012-04-11 08:00 891JDK 线程池 Executors.newCachedT ... -
利用 Spring 和 EHCache 做方法缓存处理〔转〕
2012-04-09 09:49 831利用 Spring 和 EHCache 做方法缓存处理〔 ... -
EhCache使用详细介绍
2012-04-09 09:49 1344EhCache使用详细介绍 Ehcache中不仅可 ... -
HashMap 分析
2012-04-01 08:21 1892http://www.blogjava.net ...
相关推荐
冒泡排序:应用Java和Python实现冒泡排序算法 冒泡排序:应用Java和Python实现冒泡排序算法 冒泡排序:应用Java和Python实现冒泡排序算法 冒泡排序:应用Java和Python实现冒泡排序算法 冒泡排序:应用Java和Python...
本话题主要探讨六种内部排序算法:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序以及堆排序。这六种排序算法各有优劣,适用于不同的场景,接下来我们将逐一进行详细阐述。 1. **直接插入排序**: 直接...
除了冒泡排序,代码还展示了其他两种经典的排序算法:选择排序和插入排序。 选择排序的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。...
Java排序算法实现主要涉及到两种经典的算法:冒泡排序和选择排序。这两种算法都是基于比较的排序方法,适用于小规模或教学目的的数据排序。 **冒泡排序(Bubble Sort)** 是一种简单直观的排序算法,其核心思想是...
// 实现快速排序逻辑 } } ``` 在`bubbleSort`方法中,我们可以使用两个嵌套的for循环来完成冒泡排序的过程;在`quickSort`方法中,我们需要实现分区操作,并根据返回的分割点进行递归调用。 通过这样的实现,...
本文将详细探讨十种经典的排序算法在C++中的实现,分别是冒泡排序、桶排序、计数排序、堆排序、插入排序、合并排序、快速排序、基数排序、选择排序和希尔排序。 1. **冒泡排序**:冒泡排序是最简单的排序算法之一,...
本资源介绍了六种常用的排序算法:选择排序、直接插入排序、冒泡排序、希尔排序、快速排序和堆排序。下面对每种算法进行详细介绍: 选择排序 选择排序是一种简单的排序算法。其思想是:在要排序的一组数中,选出...
这七种算法分别是:冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序和快速排序。 1. **冒泡排序**: 冒泡排序是最基础的排序算法之一,通过重复遍历待排序序列,比较相邻元素并交换位置来实现排序...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
这里我们汇总了七种常见的排序算法:Shell排序、归并排序、选择排序、快速排序、堆排序、冒泡排序和插入排序。每种算法都有其独特的特点和适用场景,下面将逐一详细介绍。 1. **Shell排序**:由Donald Shell提出,...
八种排序算法原理及Java实现是排序算法中的一种,包括冒泡排序、快速排序、直接插入排序、希尔排序、选择排序、归并排序和基数排序等。 冒泡排序是八种排序算法中的一种,属于交换排序。冒泡排序的基本思想是重复...
java可运行排序算法:①插入排序、②冒泡排序、③选择排序、④学生学号按照成绩高低排序的一个简单实例。在java工程项目的源文件src中建立Array包,可运行这四个.java文件,便于对java中的排序算法及数组结构进一步...
在本文中,我们将深入探讨四种经典的排序算法:插入排序、选择排序、基数排序和冒泡排序,以及它们在C++语言中的实现。 **插入排序(Insertion Sort)** 插入排序是一种简单直观的排序算法,它的工作原理类似于我们...
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
* 冒泡排序: * 每次在无序队列里将相邻两个数一次进行比较, * 将小数调到前面,逐次比较,直至将最大的数移到 * 最后。将剩下的N-1个数继续比较,将次大数移至 * 倒数第二位。
在提供的文件中,我们可以看到有四种经典的排序算法的Java实现:插入排序、冒泡排序、选择排序以及希尔排序。 **插入排序**: 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据...
排序算法汇总P: 冒泡排序快速排序直接选择排序插入排序希尔排序 堆排序........
本篇文章将详细讨论几种常见的排序算法:选择排序、冒泡排序、插入排序、合并排序以及快速排序,分析它们的算法原理、时间效率,并通过经验分析验证理论分析的准确性。 **1. 选择排序(Selection Sort)** 选择排序...
本文将探讨如何使用这两种语言实现几种基本的排序算法:冒泡排序、选择排序,以及两种全比较排序(并行和串行)。 首先,让我们了解一下排序算法。排序是计算机科学中最基础的操作之一,它涉及到将一组数据按照特定...
希尔排序的时间复杂度通常比插入排序要好,但不如其他更高效的排序算法,如快速排序或归并排序。 3. **冒泡排序**: 冒泡排序是一种直观的排序算法,通过不断交换相邻的逆序元素来逐渐排序整个数组。在每一轮迭代...