- 浏览: 303271 次
- 性别:
- 来自: 郴州
文章分类
- 全部博客 (70)
- hadoop (0)
- lucene (1)
- heritrix (1)
- webservice (0)
- css+div (0)
- java (29)
- javaweb (3)
- spring (2)
- hibernate (3)
- struts (5)
- struts2 (3)
- tomcat (1)
- map/reduce (0)
- ajax (0)
- android (3)
- oracle (3)
- 面试题 (1)
- 生活 (0)
- 开发工具 (1)
- 面试实习 (0)
- 设计模式 (3)
- 数据结构 (5)
- 论坛 (2)
- flex (3)
- PureMVC (1)
- java,jdk (1)
- sql server (1)
- 报表 (1)
- 算法 (4)
- 工作 (0)
最新评论
-
lp895876294:
第三种方式类似于工厂方法模式了
设计模式之单例模式(三种实现方式) -
xchsh12345:
如果用的是linux服务器呢
解决利用iText导出PDF报表中文乱码两种方式 -
memoryisking:
写的不错,关于Timer和TimeTask的内容网上资料挺多的 ...
Java定时调度 Timer类和TimerTask类 -
linfeng0169:
写的不错~!不过就是解释的不算好!
Calendar类add()与roll()方法的区别 -
u013606853:
好流弊的样子,LZ V5~
hibernate注解详解
常用的选择排序算法有两种:直接选择排序和堆排序。
一、直接选择排序(Straight Select Sorting) 也是一种简单的排序方法,它的基本思想是:第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R{1}~R[n-1]中选取最小值,与R[1]交换,....,
第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.
直接选择排序是不稳定的。
首先定义一个数据包装类:
直接选择排序:
对上面的算法改进,每次找到最小的数据的索引,减少交换的次数,提高算法效率:
二、堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
(1)用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
(2)大根堆排序算法的基本操作:
① 初始化操作:将R[1..n]构造为初始堆;
② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
堆排序与直接选择排序的区别
直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果,可减少比较次数。
堆排序是不稳定的。
堆排序代码实现:
一、直接选择排序(Straight Select Sorting) 也是一种简单的排序方法,它的基本思想是:第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R{1}~R[n-1]中选取最小值,与R[1]交换,....,
第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.
直接选择排序是不稳定的。
首先定义一个数据包装类:
//定义一个数据包装类 public class DataWrap implements Comparable<DataWrap> { int data; String flag; public DataWrap(int data, String flag) { this.data = data; this.flag = flag; } public String toString() { return data + flag; } //根据data实例变量来决定两个DataWrap的大小 public int compareTo(DataWrap dw) { return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1); } }
直接选择排序:
public class SelectSort { public static void selectSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; //依次进行n-1趟比较, 第i趟比较将第i大的值选出放在i位置上。 for (int i = 0; i < arrayLength - 1 ; i++ ) { //第i个数据只需和它后面的数据比较 for (int j = i + 1 ; j < arrayLength ; j++ ) { //如果第i位置的数据 > j位置的数据, 交换它们 if (data[i].compareTo(data[j]) > 0) { DataWrap tmp = data[i]; data[i] = data[j]; data[j] = tmp; } } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(21 , ""), new DataWrap(30 , ""), new DataWrap(49 , ""), new DataWrap(30 , "*"), new DataWrap(16 , ""), new DataWrap(9 , "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); selectSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
对上面的算法改进,每次找到最小的数据的索引,减少交换的次数,提高算法效率:
public class SelectSort2 { public static void selectSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; //依次进行n-1趟比较, 第i趟比较将第i大的值选出放在i位置上。 for (int i = 0; i < arrayLength - 1 ; i++ ) { //minIndex永远保留本趟比较中最小值的索引 int minIndex = i ; //第i个数据只需和它后面的数据比较 for (int j = i + 1 ; j < arrayLength ; j++ ) { //如果第minIndex位置的数据 > j位置的数据 if (data[minIndex].compareTo(data[j]) > 0) { //将j的值赋给minIndex minIndex = j; } } //每趟比较最多交换一次 if (minIndex != i) { DataWrap tmp = data[i]; data[i] = data[minIndex]; data[minIndex] = tmp; } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(21 , ""), new DataWrap(30 , ""), new DataWrap(49 , ""), new DataWrap(30 , "*"), new DataWrap(16 , ""), new DataWrap(9 , "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); selectSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
二、堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
(1)用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
(2)大根堆排序算法的基本操作:
① 初始化操作:将R[1..n]构造为初始堆;
② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
堆排序与直接选择排序的区别
直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果,可减少比较次数。
堆排序是不稳定的。
堆排序代码实现:
public class HeapSort { public static void heapSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; //循环建堆 for (int i = 0; i < arrayLength - 1 ; i++ ) { //建堆 builMaxdHeap(data , arrayLength - 1 - i); //交换堆顶和最后一个元素 swap(data , 0 , arrayLength - 1 - i); System.out.println(java.util.Arrays.toString(data)); } } //对data数组从0到lastIndex建大顶堆 private static void builMaxdHeap(DataWrap[] data , int lastIndex) { //从lastIndex处节点(最后一个节点)的父节点开始 for (int i = (lastIndex - 1) / 2 ; i >= 0 ; i--) { //k保存当前正在判断的节点 int k = i; //如果当前k节点的子节点存在 while (k * 2 + 1 <= lastIndex) { //k节点的左子节点的索引 int biggerIndex = 2 * k + 1; //如果biggerIndex小于lastIndex,即biggerIndex + 1 //代表的k节点的右子节点存在 if (biggerIndex < lastIndex) { //如果右子节点的值较大 if(data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) { //biggerIndex总是记录较大子节点的索引 biggerIndex++; } } //如果k节点的值小于其较大子节点的值 if(data[k].compareTo(data[biggerIndex]) < 0) { //交换它们 swap(data , k , biggerIndex); //将biggerIndex赋给k,开始while循环的下一次循环, //重新保证k节点的值大于其左、右子节点的值。 k = biggerIndex; } else { break; } } } } //交换data数组中i、j两个索引处的元素 private static void swap(DataWrap[] data , int i , int j) { DataWrap tmp = data[i]; data[i] = data[j]; data[j] = tmp; } public static void main(String[] args) { DataWrap[] data = { new DataWrap(21 , ""), new DataWrap(30 , ""), new DataWrap(49 , ""), new DataWrap(30 , "*"), new DataWrap(21 , "*"), new DataWrap(16 , ""), new DataWrap(9 , "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); heapSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
发表评论
-
利用微软翻译API替代被停用谷歌翻译API
2012-02-13 13:37 10334众所周知,谷歌已经不支持翻译API1版本了,现在提供了A ... -
(转)Java回调实现
2011-12-08 14:38 1128Java回调实现 轮询:过10分钟就到女朋友宿舍前面去看她有 ... -
java实现排序算法之插入排序(直接插入排序、折半插入、shell排序)
2011-09-15 09:29 2477插入排序主要包括直接插入排序、shell排序和折半插入等几种排 ... -
java实现排序算法之交换排序(冒泡排序、快速排序)
2011-09-14 21:28 2588交换排序的主体操作是对数组中的数据不断进行交换操作。交换排序主 ... -
java 实现数据结构之队列
2011-09-14 15:27 12599队列是一种特殊的线性表,它只允许在表的前端(front)进行删 ... -
java 实现数据结构之线性表
2011-09-14 11:44 10665应用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数 ... -
java 实现undo和redo操作链表的一种实现
2011-09-14 10:32 2132今天在iteye论坛逛,发现有这么一道笔试题目:实现一个可以增 ... -
jdbc连接mysql oracle sql server数据库的连接字符串
2011-09-13 10:41 2708jdbc连接mysql oracle sql serv ... -
java 利用label标记退出多重循环
2011-09-10 09:16 12025学过C语言的都知道,有个goto关键字,利用goto关键字可以 ... -
一个小学弟问我的算法问题
2011-09-04 20:08 1627在实验室的本科群中,一个小弟问我一个算法问题。说有1,2, ... -
深入JDK源代码之定时操作Timer类和TimerTask类实现
2011-07-26 14:45 3460Timer类是一种线程设施,可以用来实现某一个时间或某 ... -
(转)Java中对象的深复制(深克隆)和浅复制(浅克隆)
2011-07-25 20:31 11931.浅复制与深复制概念 ⑴浅复制(浅克隆) 被复制对象 ... -
深入JDK源代码之LinkedList类
2011-07-26 09:09 1883public class LinkedList<E> ... -
Java中的transient关键字
2011-07-25 14:36 24882transient说明一个属性是临时的,不会被序列化。 下面是 ... -
深入JDK源代码之Observer接口和Observable类实现观察者模式
2011-07-25 11:46 3406一、何为观察者模式? 观察者模式(有时又被称为发布/ ... -
深入JDK源代码之ArrayList类
2011-07-22 11:19 2909public class ArrayList<E&g ... -
深入JDK源代码之Arrays类中的排序查找算法
2011-07-22 09:58 3941最近在暑假实习, ... -
java 实现数据结构之栈
2011-07-10 21:51 4636在学数据结构课程 ... -
Java定时调度 Timer类和TimerTask类
2011-07-10 15:38 23874Timer类是一种线程设施,可以用来实现某一个时间或某一段 ... -
Calendar类add()与roll()方法的区别
2011-07-06 22:45 10928JDK API中对这两个方法的说明如下: abstract ...
相关推荐
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
堆排序算法 java
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
堆排序算法Java实现
用Java实现的堆排序算法,二叉树转换为堆,然后排序
堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序
heapSort 方法实现了堆排序算法。它使用以下步骤进行排序: 构建最大堆:从非叶子节点开始向上调整,使得父节点的值大于等于子节点的值。 排序阶段:依次从堆顶(最大值)开始,将堆顶元素与末尾元素交换,然后...
详解Java常用排序算法-堆排序
Java实现八大排序算法,算法描述以及代码实现, 1. 直接插入排序 2. 希尔排序 3. 简单选择排序 4. 堆排序 5. 冒泡排序 6. 快速排序 7. 归并排序 8. 基数排序
一个堆排序算法 c++写的 逻辑相同 可自行 改为java 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一...
用java对常用排序算法进行分析与实现.包含: 插入排序 直接插入排序、希尔排序 • 选择排序 简单选择排序、堆排序 • 交换排序 冒泡排序、快速排序 • 归并排序 • 基数排序
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
idea项目:一个主类选择调用6个排序类,记录了学习排序算法的过程,可以自己更改优化,每一种排序是一个类,有需要可以copy走,可重用性强
Java中常见的排序算法 1.直接插入排序 2.希尔排序 3.选择排序 4.冒泡排序 5.归并排序 6.快速排序 7.堆排序 8.计数排序 9.桶排序 10.基数排序 包含这十种算法的讲解以及动态图解(ppt)和java实现
Java各种排序算法集合: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(箱排序、基数排序)
用Java语言实现的各种排序,包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。 插入排序: package org.rut.util.algorithm.support; import org.rut.util.algorithm....
实现了四类排序算法,插入排序、交换排序、选择排序、归并排序,详情请看文档,其中 树形选择排序算法--选择排序、 堆排序--选择排序 这两种算法还没实现,有兴趣的自行解决
堆排序算法的java实现,采用大根堆。时间复杂度为O(nlogn).
几种内部排序算法的Java实现 各种内部排序方法的比较 直接插入排序 折半插入排序 希尔排序 起泡排序 快速排序 简单选择排序 树形选择排序 堆排序 归并排序 基数排序