- 浏览: 262310 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
小清新雪仔_:
报错The import org.springframewor ...
Spring Security oAuth学习之Hello World -
hrybird:
http://www.dolit.cn/portfolios/ ...
LightVOD P2P点播系统完全开源 -
xiaoxiao_qiang:
感谢,正在学习oAuth,有机会一起交流
Spring Security oAuth学习之Hello World -
thinkgem:
你好,lightvodcode.zip现在不能下了,能否发我一 ...
LightVOD P2P点播系统完全开源 -
gdw520:
<div style="text-align: ...
如何实现javascript截图 jQuery插件imgAreaSelect使用详解
package algorithms;
/**
* @author
*
*/
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,从而完成排序:
package algorithms;
/**
* @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从而完成排序。)
package algorithms;
/**
* @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个元素了。
package algorithms;
/**
* @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排序的时候采用该增量序列
package algorithms;
/**
* @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)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。
快速排序的核心在于分割算法,也可以说是最有技巧的部分。
package algorithms;
/**
* @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;
}
}
/**
* @author
*
*/
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,从而完成排序:
package algorithms;
/**
* @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从而完成排序。)
package algorithms;
/**
* @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个元素了。
package algorithms;
/**
* @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排序的时候采用该增量序列
package algorithms;
/**
* @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)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。
快速排序的核心在于分割算法,也可以说是最有技巧的部分。
package algorithms;
/**
* @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;
}
}
发表评论
-
【工具】ANT的安装和配置(windows)
2011-08-16 13:07 9711、下载:到ANT官方网站http://ant.apache. ... -
使用Axis开发Web Service程序
2011-06-16 08:32 856今天差点又要在公司加 ... -
flowplayer的破解
2011-04-24 13:53 9278这些天作视频项目时用到了开源的flowplayer,再网上下了 ... -
网站开发流程-WEB开发的流程
2011-04-21 08:18 11261. web开发流程概括 1.) ... -
Java调用linux命令ffmpeg视频转码
2011-04-01 17:54 1939Java调用linux命令ffmpeg视频转码 java.i ... -
FFmpeg linux下標准安裝 及 web使用
2011-04-01 17:53 35911,下載LAME(Lame Aint an MP3 Encod ... -
安装和使用ffmpeg转换视频为flv文件(windows和linux)
2011-04-01 17:49 2076安装和使用ffmpeg转换视频为flv文件(windows和l ... -
java调用dll
2011-03-02 17:34 1749一.在程序用jnative调用window的dll 1. ... -
java处理日期时间 相加减
2011-02-28 16:33 948JAVA处理日期时间常用方法: 1.java.util.C ... -
java随机生成十六进制颜色
2010-12-17 09:02 7559/** * 获取十六进制的颜色代码.例如 &qu ... -
java保留小数位问题
2010-12-08 16:07 2128java保留两位小数问题: 补充 (double)(Ma ... -
要和.net进行一次交互HTTPt发过来的XML格式
2010-08-13 15:05 1075今天干活时有个需求,要和.net进行一次交互,想在Struts ... -
LightVOD P2P点播系统完全开源
2010-06-21 09:55 6364http://www.lightvod.com 源码下载及配 ... -
The content of element type "web-app" must match解决
2010-01-26 12:46 1855The content of element type &qu ... -
JAVA错误处理大集合
2009-12-23 15:29 17290、 需要标识符 a) 不在函数内 1、 非法表达式开始 b) ... -
飞信API(fetionlib)--发送短信
2009-12-03 10:39 2812package com.test; import java. ...
相关推荐
**算法与程序设计VB排序复习概述** 排序是计算机科学中基础且重要的问题,尤其是在数据处理和分析中。VB(Visual Basic)是一种常用的编程语言,它提供了实现各种排序算法的工具。本PPT课件主要围绕两种基本排序...
【知识点解析】 ...以上是对【标题】"四年级语文(上册)错乱句子排序复习题与答案.doc"及其【描述】中涉及的知识点的详细解析,主要涵盖了语文学习的基本技能、思维训练、文化熏陶和教学方法等方面。
中考语文句子衔接与排序复习专题.docx
人教四年级下册语文句子排序复习PPT教案.pptx
这篇博客"JAVA 排序复习"可能涵盖了各种排序算法的原理、实现以及在实际开发中的应用。 首先,让我们了解一下排序的基本类型。主要有两种分类:内部排序(数据在内存中完成排序)和外部排序(数据量太大,需要借助...
人教版四年级下册语文句子排序复习PPT教案.pptx
第28周-第01章节-Python3.5-堆排序复习.mp4
河北省唐山市滦南县中考语文句子衔接与排序复习专题新人教版20180528316
1. 句子衔接与排序是语文学习中的一个重要部分,主要考察学生的语言组织能力和逻辑思维能力。在解答这类题目时,需要考虑句子之间的逻辑关系,如因果关系、递进关系、并列关系等。 2. 例题1中,通过分析四个句子,...
【标题】和【描述】提到的是中考语文复习练习中的句子衔接与排序题目,这是一类考查语言逻辑和表达连贯性的试题。此类题目的目的是检验学生能否根据上下文语境,正确理解和组织句子,使文段意思通顺,逻辑严密。 ...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。...通过阅读并实践这个"快速排序复习1"的压缩包文件,你可以更好地掌握快速排序的实现细节,并能运用到自己的C#编程实践中。
快速排序算法复习.md
在IT行业中,算法是开发者的核心竞争力之一,特别是对于Java...因此,不断学习和复习算法是每个开发者都应该重视的事项。无论是在应对技术面试,还是在日常开发中优化代码性能,扎实的算法基础都能为你提供强大的支持。
本复习题主要涵盖了排序算法的基础知识和常见类型,旨在帮助学习者巩固和深化对排序算法的理解。** 在数据结构中,排序算法通常分为内部排序(数据量较小,可在内存中完成)和外部排序(数据量巨大,需要借助磁盘等...
中考语文句子排序专题复习全面.pptx
算法复习资料是学习和提升编程技能的重要资源,涵盖了数据结构、排序、搜索、图论等多个方面。本文将深入探讨这些关键知识点,帮助你巩固和提高对算法的理解。 首先,我们来谈谈数据结构。数据结构是组织和存储数据...
主要有直接插入排序,选择排序,冒泡排序,二分排序,shell排序等等
### C语言之排序总结 #### 一、简介 在计算机科学与技术领域,排序算法是数据结构中的一个重要组成部分,尤其对于参加计算机二级机考的学生来说,掌握几种经典的排序方法至关重要。本文将详细介绍几种常见的排序...