没有合适的资源?快使用搜索试试~ 我知道了~
首页Java排序算法(桶排序,基数排序等)
资源详情
资源评论
资源推荐
排序算法复习(Java 实现)(一): 插入,冒泡,选择,Shell,快速排序
为了便于管理,先引入个基础类:
package algorithms;
/**
* @author yovn
*
*/
public abstract class Sorter<E extends Comparable<E>> {
public abstract void sort(E[] array,int from ,int len);
public 'nal void sort(E[] array)
{
sort(array,0,array.length);
}
protected 'nal 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 'nal 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 'nal 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> {
剩余15页未读,继续阅读
yuchensmile
- 粉丝: 1
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1