基于Java的不同排序算法的实现及其性能比较 - 下载频道 - CSDN.NET
&&&&基于Java的不同排序算法的实现及其性能比较
&基于Java的不同排序算法的实现及其性能比较
基于java语言，通过实验，详细对比了几种常见的排序算法的性能
若举报审核通过，可奖励20下载分
被举报人：
liweiminlilin
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：
您可能还需要
Q.为什么我点的下载下不了，但积分却被扣了
A. 由于下载人数众多，下载服务器做了并发的限制。若发现下载不了，请稍后再试，多次下载是不会重复扣分的。
Q.我的积分不多了，如何获取积分？
A. 获得积分，详细见。
完成任务获取积分。
评价资源返积分。
论坛可用分兑换下载积分。
第一次绑定手机，将获得5个C币，C币可。
下载资源意味着您已经同意遵守以下协议
资源的所有权益归上传用户所有
未经权益所有人同意，不得将资源中的内容挪作商业或盈利用途
CSDN下载频道仅提供交流平台，并不能对任何下载资源负责
下载资源中如有侵权或不适当内容，
本站不保证本站提供的资源的准确性，安全性和完整性，同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
课程资源下载排行
积分不够下载该资源
如何快速获得积分？
你下载资源过于频繁，请输入验证码
如何快速获得积分？
你已经下载过该资源，再次下载不需要扣除积分
基于Java的不同排序算法的实现及其性能比较
所需积分：3
剩余积分：
VIP会员，免积分下载
会员到期时间：日
剩余下载次数：1000
VIP服务公告:Java数组排序总结(冒泡,选择,插入,希尔)
递归算法的复杂度_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
Java数组排序总结(冒泡,选择,插入,希尔)
递归算法的复杂度
上传于||文档简介
&&J​a​v​a​数​组​排​序​总​结​(​冒​泡​,​选​择​,​插​入​,​希​尔​)
阅读已结束，如果下载本文需要使用
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩11页未读，继续阅读
你可能喜欢57520人阅读
经典排序算法（Java版）
权当复习，以备引用（理论来源于：，感谢该网站。JAVA源码为我所写）
1、冒泡排序 Bubble Sort
最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。这个算法可实现如下。
算法如下：
&&& &*冒泡排序
&&& &*@paramsrc待排序数组
&&& void doBubbleSort(int[] src)
&&&&&& int len=src.length;
&&&&&& for(int i=0;i&i++)
&&&&&&&&&& for(int j=i+1;j&j++)
&&&&&&&&&& {
&&&&&&&&&&&&& int
&&&&&&&&&&&&& if(src[i]&src[j])
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&& temp=src[j];
&&&&&&&&&&&&&&&&& src[j]=src[i];
&&&&&&&&&&&&&&&&& src[i]=
&&&&&&&&&&&&& }&&&&&&&&&&&&
&&&&&&&&&& }
&&&&&&&&&& printResult(i,src);
&&&&&& }&&&&&
2、选择排序 Selection Sort
选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。　　当然，实际操作时，也可以根据需要，通过从待排序的记录中选择最大者与其首记录交换位置，按从大到小的顺序进行排序处理。
算法如下：
&&&&&& /**
&&& &*选择排序
&&& &*@paramsrc待排序的数组
&&& void doChooseSort(int[] src)
&&&&&& int len=src.length;
&&&&&& int
&&&&&& for(int i=0;i&i++)
&&&&&&&&&& temp=src[i];
&&&&&&&&&& int
&&&&&&&&&& int samllestLocation=i;//最小数的下标
&&&&&&&&&& for(j=i+1;j&j++)
&&&&&&&&&& {
&&&&&&&&&&&&& if(src[j]&temp)
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&& temp=src[j];//取出最小值
&&&&&&&&&&&&&&&&& samllestLocation=j;//取出最小值所在下标
&&&&&&&&&&&&& }
&&&&&&&&&& }
&&&&&&&&&& src[samllestLocation]=src[i];
&&&&&&&&&& src[i]=
&&&&&&&&&& printResult(i,src);
3、插入排序 Insertion Sort
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]?騆[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。　　简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序，折半插入排序留到“查找”内容中进行。　　图1演示了对4个元素进行直接插入排序的过程，共需要(a),(b),(c)三次插入。
图1 对4个元素进行插入排序
在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型ElementType中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L[i]是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将L[i]放入L[0]中，这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。
算法如下：
&&& &*插入排序(WHILE循环实现)
&&& &*@paramsrc待排序数组
&&& void doInsertSort1(int[] src)
&&&&&& int len=src.length;
&&&&&& for(int i=1;i&i++)
&&&&&& {&&
&&&&&&&&&& int temp=src[i];
&&&&&&&&&& int j=i;
&&&&&&&&&&
&&&&&&&&&& while(src[j-1]&temp)
&&&&&&&&&& {
&&&&&&&&&&&&& src[j]=src[j-1];
&&&&&&&&&&&&& j--;
&&&&&&&&&&&&& if(j&=0)
&&&&&&&&&&&&&&&&& break;
&&&&&&&&&& }
&&&&&&&&&& src[j]=
&&&&&&&&&& printResult(i+1,src);
&&& &*插入排序(FOR循环实现)
&&& &*@paramsrc待排序数组
&&& void doInsertSort2(int[] src)
&&&&&& int len=src.length;
&&&&&& for(int i=1;i&i++)
&&&&&&&&&& int
&&&&&&&&&& int temp=src[i];
&&&&&&&&&& for(j=i;j&0;j--)
&&&&&&&&&& {
&&&&&&&&&&&&& if(src[j-1]&temp)
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&& src[j]=src[j-1];
&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&& }else//如果当前的数，不小前面的数，那就说明不小于前面所有的数，
&&&&&&&&&&&&&&&&& &//因为前面已经是排好了序的，所以直接通出当前一轮的比较
&&&&&&&&&&&&&&&&& break;
&&&&&&&&&& }
&&&&&&&&&& src[j]=
&&&&&&&&&& printResult(i,src);
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：4889725次
积分：50291
积分：50291
排名：第33名
原创：462篇
转载：209篇
译文：28篇
评论：1564条
(3)(7)(7)(10)(3)(5)(2)(3)(10)(3)(1)(10)(8)(1)(1)(11)(13)(18)(9)(5)(2)(13)(14)(31)(1)(1)(2)(3)(4)(13)(3)(1)(12)(6)(4)(6)(4)(2)(1)(6)(15)(35)(11)(3)(2)(25)(2)(3)(13)(2)(5)(2)(1)(15)(5)(7)(8)(41)(33)(54)(40)(7)(2)(4)(1)(12)(17)(3)(8)(8)(1)(55)用心创造滤镜
扫码下载App
汇聚2000万达人的兴趣社区下载即送20张免费照片冲印
扫码下载App
温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
磨练性格以微笑
面对痛苦是人生
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(514)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
在LOFTER的更多文章
loftPermalink:'',
id:'fks_',
blogTitle:'java 排序算法性能分析',
blogAbstract:'import java.util.Rpublic class SortTest {&& &/** && & * 排序测试类 && & * &&& & * 排序算法的分类如下： 1.插入排序（直接插入排序、折半插入排序、希尔排序）； 2.交换排序（冒泡泡排序、快速排序）； && & * 3.选择排序（直接选择排序、堆排序）； 4.归并排序； 5.基数排序。 && & * &&& & * 关于排序方法的选择： (1)若n较小(如n≤50)，可采用直接插入或直接选择排序。 ',
blogTag:'java排序,数据结构',
blogUrl:'blog/static/1',
isPublished:1,
istop:false,
modifyTime:2,
publishTime:5,
permalink:'blog/static/1',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'磨练性格以微笑\r\n面对痛苦是人生',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}java数据结构和算法
Java数据结构和算法
一、数组于简单排序
........................................................... 1
二、栈与队列
................................................................
....................................................................
...................................................................
五、哈希表
.................................................................
六、高级排序
...............................................................
七、二叉树
.................................................................
八、红—黑树
...............................................................
.....................................................................
十、带权图
.................................................................
一、数组于简单排序
数组（array）是相同类型变量的集合，可以使用共同的名字引用它。数组可被定义为任何类型，可以是一维或多维。数组中的一个特别要素是通过下标来访问它。数组提供了一种将有联系的信息分组的便利方法。
一维数组（one‐dimensional array
）实质上是相同类型变量列表。要创建一个数组，你必须首先定义数组变量所需的类型。通用的一维数组的声明格式是：
type var‐name[ ];
获得一个数组需要2步。第一步，你必须定义变量所需的类型。第二步，你必须使用运算符new来为数组所要存储的数据分配内存，并把它们分配给数组变量。这样Java
中的数组被动态地分配。如果动态分配的概念对你陌生，别担心，它将在本书的后面详细讨论。
数组的初始化（array initializer ）就是包括在花括号之内用逗号分开的表达式的列表。逗号分开了数组元素的值。Java
会自动地分配一个足够大的空间来保存你指定的初始化元素的个数，而不必使用运算符new。
Java 严格地检查以保证你不会意外地去存储或引用在数组范围以外的值。Java
的运行系统会检查以确保所有的数组下标都在正确的范围以内（在这方面，
Java 与C/C++ 从根本上不同，C/C++ 不提供运行边界检查）。
在Java 中，多维数组（multidimensional arrays
）实际上是数组的数组。你可能期望，这些数组形式上和行动上和一般的多维数组一样。然而，你将看到，有一些微妙的差别。定义多维数组变量要将每个维数放在它们各自的方括号中。例如，下面语句定义了一个名为twoD
的二维数组变量。
int twoD[][] = new int[4][5];
简单排序中包括了：冒泡排序、选择排序、插入排序；
1.冒泡排序的思想：
假设有N个数据需要排序，则从第0个数开始，依次比较第0和第1个数据，如果第0个大于第1个则两者交换，否则什么动作都不做，继续比较第1个第2个…，这样依次类推，直至所有数据都“冒泡”到数据顶上。
冒泡排序的的java代码：
Public void bubbleSort()
for(out=nElems‐1;out&0;out‐‐)
for(in=0;in&in++)
If(a[in]&a[in+1])
Swap(in,in+1);
算法的不变性：许多算法中，有些条件在算法执行过程中始终是不变的。这些条件被称
为算法的不变性，如果不变性不为真了，则标记出错了；
冒泡排序的效率O（N*N），比较N*N/2，交换N*N/4；
2. 选择排序的思想：
假设有N条数据，则暂且标记第0个数据为MIN（最小），使用OUT标记最左边未排序的数据，然后使用IN标记第1个数据，依次与MIN进行比较，如果比MIN小，则将该数据标记为MIN，当第一轮比较完后，最终的MIN与OUT标记数据交换，依次类推；
选择排序的java代码：
Public void selectSort()
Int in,out,
For(out=0;out&nElems‐1;out++)
For(in=out+1;in&nEin++)
If(a[in]&a[min])
Swap(out,min);
选择排序的效率：O（N*N），比较N*N/2，交换&N；
选择排序与冒泡排序比较，比较次数没有明显改变，但交换次数明显减少了很多；
3. 插入排序的思想：
插入排序是在部分数据有序的情况下，使用OUT标记第一个无序的数据，将其提取保存到一个中间变量temp中去，使用IN标记空位置，依次比较temp中的值与IN‐1的值，如果IN‐值大于temp的值，则后移，直到遇到第一个比temp小的值，在其下一个位置插入；
插入排序的java代码：
Public void InsertionSort()
For(out=1;out&nEout++)
Long temp=a[out]
While(in&0&&
a[in‐1]&temp)
A[in]=a[in‐1];
‐ ‐
插入排序的效率：O（N*N）,
比较N*N/4，复制N*N/4；插入排序在随机数的情况下，比冒泡快一倍，比选择稍快；在基本有序的数组中，插入排序几乎只需要O（N）；在逆序情况下，并不比冒泡快；
二、栈与队列
1、栈的定义 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。 (2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
【示例】元素是以a1，a2，…，an的顺序进栈，退栈的次序却是an，an-1，…，a1。 2、栈的基本运算
（1）InitStack（S） 构造一个空栈S。 （2）StackEmpty（S）
判栈空。若S为空栈，则返回TRUE，否则返回FALSE。 （3）StackFull（S）
判栈满。若S为满栈，则返回TRUE，否则返回FALSE。 注意： 该运算只适用于栈的顺序存储结构。 （4）Push（S，x）
进栈。若栈S不满，则将元素x插入S的栈顶。 （5）Pop（S） 退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。
（6）StackTop（S） 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
队列的定义及基本运算 1、定义 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
（1）允许删除的一端称为队头（Front）。 （2）允许插入的一端称为队尾（Rear）。 （3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。
【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…，an。
2、队列的基本逻辑运算 （1）InitQueue（Q） 置空队。构造一个空队列Q。 （2）QueueEmpty（Q）
判队空。若队列Q为空，则返回真值，否则返回假值。 （3） QueueFull（Q）
判队满。若队列Q为满，则返回真值，否则返回假值。 注意：此操作只适用于队列的顺序存储结构。 （4） EnQueue（Q，x）
若队列Q非满，则将元素x插入Q的队尾。此操作简称入队。 （5） DeQueue（Q）
若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称出队。 （6） QueueFront（Q）
若队列Q非空，则返回队头元素，但不改变队列Q的状态。
在链表中，每个数据项都被包含在‘点“中，一个点是某个类的对象，这个类可认叫做LINK。因为一个链表中有许多类似的链结点，所以有必要用一个不同于链表的类来表达链结点。每个LINK对象中都包含一个对下一个点引用的字段（通常叫做next）但是本身的对象中有一个字段指向对第一个链结点的引用
用一组地址任意的存储单元存放线性表中的数据元素。
以元素(数据元素的映象)
+ 指针(指示后继元素存储位置)
(表示数据元素 或 数据元素的映象)
以“结点的序列”表示线性表
称作线性链表（单链表）⎯⎯
单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。
因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i
1、链接存储方法
链接方式存储的线性表简称为链表（Linked List）。
链表的具体存储表示为：
① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。
2、链表的结点结构
┌──┬──┐
│data│next│
└──┴──┘
data域--存放结点值的数据域
next域--存放结点的直接后继的地址（位置）的指针域（链域）
①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
②每个结点只有一个链域的链表称为单链表（Single Linked List）。
【例】线性表（bat，cat，eat，fat，hat，jat，lat，mat）的单链表示如示意图
3、头指针head和终端结点指针域的表示
单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。
链表由头指针唯一确定，单链表可以用头指针的名字来命名。
【例】头指针名是head的链表可称为表head。
终端结点无后继，故终端结点的指针域为空，即NULL。
4、单链表的一般图示法
由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（bat，cat，fat，hat，jat，lat，mat）的单链表就可以表示为下图形式。
5、单链表类型描述
typedef char DataT //假设结点的数据域类型为字符
typedef struct node{ //结点类型定义
DataT //结点的数据域
struct node *//结点的指针域
typedef ListNode *LinkL
ListNode *p;
①*LinkList和ListNode是不同名字的同一个指针类型（命名的不同是为了概念上更明确）
②*LinkList类型的指针变量head表示它是单链表的头指针
③ListNode类型的指针变量p表示它是指向某一结点的指针
6、指针变量和结点变量
┌────┬────────────┬─────────────┐
│ │ 指针变量 │ 结点变量 │
├────┼────────────┼─────────────┤
│ 定义 │在变量说明部分显式定义 │在程序执行时，通过标准 │
│ │ │函数malloc生成 │
├────┼────────────┼─────────────┤
│ 取值 │ 非空时，存放某类型结点 │实际存放结点各域内容 │
│ │的地址 │ │
├────┼────────────┼─────────────┤
│操作方式│ 通过指针变量名访问 │ 通过指针生成、访问和释放 │
└────┴────────────┴─────────────┘
①生成结点变量的标准函数
p=( ListNode *)malloc(sizeof(ListNode))；
//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中
②释放结点变量空间的标准函数
free(p)；//释放p所指的结点变量空间
③结点分量的访问
利用结点变量的名字*p访问结点分量
方法一：(*p).data和(*p).next
方法二：p-﹥data和p-﹥next
④指针变量p和结点变量*p的关系
指针变量p的值——结点地址
结点变量*p的值——结点内容
(*p).data的值——p指针所指结点的data域的值
(*p).next的值——*p后继结点的地址
*((*p).next)——*p后继结点
若指针变量p的值为空（NULL），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。
② 有关指针类型的意义和说明方式的详细解释
可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。
因此，在单链表中第 i 个结点之前进行插入的基本操作为:
找到线性表中第i-1个结点，然后修改其指向后继的指针。
双端链表与传统的链表非常相似，但是它有一个新增的特性：即对最后一个链结点的引用，就像对第一个链结点的引用一样。
对最后一个链结点的引用允许像在表头一样，在表尾直接插入一个链结点。当然，仍然可以在普通的单链表的表尾插入一个链结点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。
对最后一个链结点的引用允许像在表头一样，在表尾直接插入一个链结点。当然，仍然可以在普通的单链表的表尾插入一个链结点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。
像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便操作的场合，队列的实现就是这样一个情况。
下面是一个双端链表的例子。
class Link3{
public long dD
public Link3
//............................
public Link3(long d){
//............................
public void displayLink(){
System.out.print(dData+" ");
///////////////////////////////////
class FirstLastList{
private Link3
private Link3
//............................
public FirstLastList(){
//.............................
public boolean isEmpty(){
return first==
//.............................
public void insertFirst(long dd){
Link3 newLink=new Link3(dd);
if(isEmpty())
newLink.next=
first=newL
//...........................
public void insertLast(long dd){
Link3 newLink=new Link3(dd);
if(isEmpty())
first=newL
last.next=newL
//...............................
public long deleteFirst(){
long temp=first.dD
if(first.next==null)
first=first.
//.......................................
public void displayList(){
System.out.print("List (first--&last): ");
Link3 current=
while(current!=null){
current.displayLink();
current=current.
System.out.println("");
/////////////////////////////////////
public class FirstLastApp {
public static void main(String[] args) {
FirstLastList theList=new FirstLastList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);
theList.displayList();
theList.deleteFirst();
theList.deleteFirst();
theList.displayList();
为了简单起见，在这个程序中，把每个链结点中的数据字段个数从两个压缩到一个。这更容易显示链结点的内容。（记住，在一个正式的程序中，可能会有非常多的数据字段，或者对另外一个对象的引用，那个对象也包含很多数据字段。）
这个程序在表头和表尾各插入三个链点，显示插入后的链表。然后删除头两个链结点，再次显示。
注意在表头重复插入操作会颠倒链结点进入的顺序，而在表尾的重复插入则保持链结点进入的顺序。
双端链表类叫做FirstLastList。它有两个项，first和last，一个指向链表中的第一个链结点，另一个指向最后一个链结点。如果链表中只有一个链结点，first和last就都指向它，如果没有链结点，两者都为Null值。
这个类有一个新的方法insertLast()，这个方法在表尾插入一个新的链结点。这个过程首先改变last.next，使其指向新生成的链结点，然后改变last，使其指向新的链结点。
插入和删除方法和普通链表的相应部分类似。然而，两个插入方法都要考虑一种特殊情况，即插入前链表是空的。如果isEmpty()是真，那么insertFirst()必须把last指向新的链结点，insertLast()也必须把first指向新的链结点。
如果用insertFirst()方法实现在表头插入，first就指向新的链结点，用insertLast()方法实现在表尾插入，last就指向新的链结点。如果链表只有一个链结点，那么多表头删除也是一种特殊情况：last必须被赋值为null值。
不幸的是，用双端链表也不能有助于删除最后一个链结点，因为没有一个引用指向倒数第二个链结点。如果最后一个链结点被删除，倒数第二个链结点的Next字段应该变成Null值。为了方便的删除最后一个链结点，需要一个双向链表。（当然，也可以遍历整个链表找到最后一个链结点，但是那样做效率不是很高。）
在有序链表中，数据是按照关键值有序排列的。有序链表的删除常常是只限于删除在链表头部的最小链结点。不过，有时也用Find()方法和Delete()方法在整个链表中搜索某一特定点。
一般，在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。但是，有序链表实现起来比有序数组更困难一些。
后而将看到一个有序链表的应用：为数据排序。有序链表也可以用于实现优先级队列，尽管堆是更常用的实现方法。
在有序链表中插入一个数据项的Java代码
为了在一个有序链表中插入数据项，算法必须首先搜索链表，直到找到合适的位置：它恰好在第一个比它大的数据项的前面。
当算法找到了要插入的位置，用通常的方式插入数据项：把新链结点的Next字段指向下一个链结点，然后把前一个链结点的Next字段改为指向新的链结点。然而，需要考虑一些特殊情况：链结点有可以插在表头，或者插在表尾。看一下这段代码：
Public void insert(long key){
Link newLink=new Link(key);
Link previous=
Link current=
While(current!=null &&
key&current.dData){
Current=current.
If(previous==null)
First=newL
Previous.next=newL
newLink.next=
在链表上移动时，需要用一个previous引用，这样才能把前一个链结点的Next字段指向新的链结点。创建新链结点后，把current变量设为first，准备搜索正确的插入点。这时也把previous设为Null值，这步操作很重要，因为后面要用这个Null值判断是否仍在表头。
While循环和以前用来搜索插入点的代码类似，但是有一个附加的条件。如果当前检查的链结点的关键值不再小于待插入的链结点的关键值，则循环结束；这是最常见的情况，即新关键值插在链表中部的某个地方。
然而，如果current为Null值，while循环也会停止。这种情况发生在表尾，或者链表为空时。
如果current在表头或者链表为空，previous将为Null值；所以让first指向新的链结点。否则current处在链表中部或结尾，就使previous的next字段指向新的链结点。
不论哪种情况、都让新链结点的Next字段指向current。如果在表尾，current为Null值，则新链结点的Next字段也本应该设为这个值（Null）。
下面是有序链表的程序
SortedList.java程序实现了一个SortedList类，它拥有insert()、remove()和displayList()方法。只有insert()方法与无序链表中的insert()方法不同。
package 有序链表;
class Link{
public long dD
public Link(long dd){
//.........................
public void displayLink(){
System.out.print(dData+" ");
////////////////////////////////////////
class SortedList{
//..........................
public SortedList(){
//.........................
public boolean isEmpty(){
return (first==null);
//..........................
public void insert(long key){
Link newLink=new Link(key);
Link previous=
Link current=
while(current!=null &&
key&current.dData){
current=current.
if(previous==null)
first=newL
previous.next=newL
newLink.next=
//................................
public Link remove(){
Link temp=
first=first.
//................................
public void displayList(){
System.out.print("List (first--&last): ");
Link current=
while(current!=null){
current.displayLink();
current=current.
System.out.println("");
public class SortedLinkApp {
public static void main(String[] args) {
SortedList theSortedList=new SortedList();
theSortedList.insert(20);
theSortedList.insert(40);
theSortedList.displayList();
theSortedList.insert(10);
theSortedList.insert(30);
theSortedList.insert(50);
theSortedList.displayList();
theSortedList.remove();
theSortedList.displayList();
System.exit(0);
在Main()方法中，插入值为20和40的两个链结点。然后再插入三个链结点，分别是10、30和50。这三个值分别插在表头、表中和表尾。这说明insert()方法正确地处理了特殊情况。最后删除了一个链结点，表现出删除操作总是从表头进行。每一步变化后，都显示整个链表。
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
typedef struct DuLNode
struct DuLNode *prior,*
}DuLNode,*DuLinkL
void InitList(DuLinkList *L)
*L=(DuLinkList)malloc(sizeof(DuLNode));
(*L)-&next=(*L)-&prior=*L;
exit(OVERFLOW);
void DestroyList(DuLinkList *L)
DuLinkList q,p=(*L)-&
while(p!=*L)
void ClearList(DuLinkList L)
DuLinkList q,p=L-&
while(p!=L)
L-&next=L-&prior=L;
Status ListEmpty(DuLinkList L)
if(L-&next==L&&L-&prior==L)
return TRUE;
return FALSE;
int ListLength(DuLinkList L)
DuLinkList p=L-&
while(p!=L)
Status GetElem(DuLinkList L,int i,ElemType *e)
DuLinkList p=L-&
while(p!=L&&
if(p==L||j&i)
return ERROR;
return OK;
int LocateElem(DuLinkList L,ElemType
e,Status(*compare)(ElemType,ElemType))
DuLinkList p=L-&
while(p!=L)
if(compare(p-&data,e))
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
DuLinkList p=L-&next-&
while(p!=L)
if(p-&data==cur_e)
*pre_e=p-&prior-&
return TRUE;
return FALSE;
Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
DuLinkList p=L-&next-&
while(p!=L)
if(p-&prior-&data==cur_e)
*next_e=p-&
return TRUE;
return FALSE;
DuLinkList GetElemP(DuLinkList L,int i)
DuLinkList p=L;
if(i&0||i&ListLength(L))
return NULL;
for(j=1;j&=i;j++)
Status ListInsert(DuLinkList L,int i,ElemType e)
DuLinkList p,s;
if(i&1||i&ListLength(L)+1)
return ERROR;
p=GetElemP(L,i-1);
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
return OVERFLOW;
s-&data=e;
s-&prior=p;
s-&next=p-&
p-&next-&prior=s;
p-&next=s;
return OK;
Status ListDelete(DuLinkList L,int i,ElemType *e)
return ERROR;
p=GetElemP(L,i);
return ERROR;
p-&prior-&next=p-&
p-&next-&prior=p-&
return OK;
void ListTraverse(DuLinkList L,void(*visit)(ElemType))
DuLinkList p=L-&
while(p!=L)
visit(p-&data);
printf("\n");
void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
DuLinkList p=L-&
while(p!=L)
visit(p-&data);
printf("\n");
迭代器是一种对象，它能够用来遍历STL容器中的部分或全部元素，每个迭代器对象代表容器中的确定的地址。迭代器修改了常规指针的接口，所谓迭代器是一种概念上的抽象：那些行为上象迭代器的东西都可以叫做迭代器。然而迭代器有很多不同的能力，它可以把抽象容器和通用算法有机的统一起来。
迭代器提供一些基本操作符：*、++、==、！=、=。这些操作和C/C++“操作array元素”时的指针接口一致。不同之处在于，迭代器是个所谓的smart
pointers，具有遍历复杂数据结构的能力。其下层运行机制取决于其所遍历的数据结构。因此，每一种容器型别都必须提供自己的迭代器。事实上每一种容器都将其迭代器以嵌套的方式定义于内部。因此各种迭代器的接口相同，型别却不同。这直接导出了泛型程序设计的概念：所有操作行为都使用相同接口，虽然它们的型别不同。
迭代器使开发人员能够在类或结构中支持foreach迭代，而不必整个实现IEnumerable或者IEnumerator接口。只需提供一个迭代器，即可遍历类中的数据结构。当编译器检测到迭代器时，将自动生成IEnumerable接口或者IEnumerator接口的Current，MoveNext和Dispose方法。
特点 1.迭代器是可以返回相同类型值的有序序列的一段代码；
2.迭代器可用作方法、运算符或get访问器的代码体；
3.迭代器代码使用yield return语句依次返回每个元素，yield break将终止迭代；
4.可以在类中实现多个迭代器，每个迭代器都必须像任何类成员一样有惟一的名称，并且可以在foreach语句中被客户端代码调用；
5.迭代器的返回类型必须为IEnumerable和IEnumerator中的任意一种；
6.迭代器是产生值的有序序列的一个语句块，不同于有一个 或多个yield语句存在的常规语句块；
7.迭代器不是一种成员，它只是实现函数成员的方式，理解这一点是很重要的，一个通过迭代器实现的成员，可以被其他可能或不可能通过迭代器实现的成员覆盖和重载；
8.迭代器块在C#语法中不是独特的元素，它们在几个方面受到限制，并且主要作用在函数成员声明的语义上，它们在语法上只是语句块而已；
递归是函数调用自身的一种特殊的编程技术，其应用主要在以下几个方面：
在java当中的基本形式是：Public void mothed（int n）{//当满足某条件时：
Mothed（n‐1）；
递归二分查找
Java二分查找实现,欢迎大家提出交流意见.
class BinarySearch&T extends
Comparable&T&& {
private T[]//要排序的数据 public BinarySearch(T[] data){ this.data
= } public int search(T key){ int
if(data == null) return -1; low = 0; high = data.length - 1;
while(low &= high){ mid = (low + high) / 2;
System.out.println("mid " + mid + " mid value:" + data[mid]);///
pareTo(data[mid]) & 0){ high = mid - 1;
}else pareTo(data[mid]) & 0){ low = mid +
1; }else pareTo(data[mid]) == 0){ } } return
-1; } private int doSearchRecursively(int low , int high , T key){
if(low &= high){ mid = (low +
high) / 2; result = pareTo(data[mid]);
System.out.println("mid " + mid + " mid value:" + data[mid]);///
if(result & 0){ return doSearchRecursively(low , mid
- 1 , key); }else if(result & 0){ return
doSearchRecursively(mid + 1 , high , key); }else if(result == 0){
} } return -1; }
public int searchRecursively(T key){ if(data ==null)return -1;
return doSearchRecursively(0 , data.length - 1 , key); } public
static void main(String[] args){ Integer[] data = {1 ,4 ,5 ,8 ,15
,33 ,48 ,77 ,96};
BinarySearch&Integer& binSearch = new
BinarySearch&Integer&(data);
//System.out.println("Key index:" + binSearch.search(33) );
System.out.println("Key index:" + binSearch.searchRecursively(3) );
//String [] dataStr = {"A" ,"C" ,"F" ,"J" ,"L" ,"N" ,"T"};
//BinarySearch&String& binSearch =
new BinarySearch&String&(dataStr);
//System.out.println("Key index:" + binSearch.search("A") ); }
其实在数组的全排序中完全可以使用更加易懂简便的写法——for循环，但是通过for循环编写数组全排序需要有一个先决条件——知道数组全排序的个数，因为有n个数据全排序就需要写n个嵌套for循环。因此在写全排序时一般使用递归方法。这就是我的第一个关于递归排序的见解——递归排序可以无需已知排序数组的长度，即排序个数！
其二，不管是使用递归进行数组排序还是使用for循环进行数组的排序，它们都是本质都是使用枚举，因此可以得出这样一个结论:枚举可以确保找出每一种可能的排序规则！
其三，枚举是列出所有的方法并找出符合要求的算法，因此其算法效率一定比较的低，需要对其进行优化，才能达到较好的效果（递归的时候排除所有不可能的方案）
消除递归的基本思路是用栈来模拟系统的函数调用从而消除递归。
基本上要做一下三件事：传递参数（包括返回地址）并转到函数入口；获得参数并处理参数；根据传入的返回地址返回
五、哈希表
一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表）。
哈希表不可避免冲突(collision)现象：对不同的关键字可能得到同一哈希地址
即key1≠key2，而f(key1)=f(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。
因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。
六、高级排序
下周提供。
七、二叉树
答：二叉树是一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。.二叉树的基本形态：(1)空二叉树；(2)只有一个根结点的二叉树；(3)右子树为空的二叉树；4)左子树为空的二叉树；(5)完全二叉树。
二叉树的存储结构 包括：
1.顺序存储结构
连续的存储单元存储二叉树的数据元素。例如图 6.4(b)的完全二叉树 , 可以向量 (一维数组 )
bt(1:6)作它的存储结构，将二叉树中编号为 i的结点的数据元素存放在分量 bt[i]中 ,如图 6.6(a)
所示。但这种顺序存储结构仅适合于完全二叉树 ,而一般二叉树也按这种形式来存储 ,这将造成存 贮浪费。如和
图 6.4(c)的二叉树相应的存储结构图 6.6(b)所示，图中以 “0”表示不存在此结点 .
2. 链式存储结构
由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点至少包含三个域
:数据域和左右指针域 ,如图 (b)所示。有时 ,为了便于找 到结点的双亲 ,则还可在结点结构中增加一个指向其双亲受的指针域，如图
6.7(c)所示。
遍历二叉树：
遍历二叉树 (traversing binary tree)的问题，
即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先 (根
)序遍历，中 (根 )序遍历和后 (根 )序遍历。
（1）前序遍历
前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的
（2）中序遍历
中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的
（3）后序遍历
后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的
八、红—黑树
概念 红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf
Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick
于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log
n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++
STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI
STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根是黑色。 性质3. 所有叶子都是黑色（叶子是NIL节点）。 性质4.
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 性质5.
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 这些约束强制了红黑树的关键性质:
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
要知道为什么这些特性确保了这个结果，注意到属性4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据属性5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
一种红黑树的实现方法：
public class RBTreeTest&E extends
Comparable&E&& {
static enum Color { BLACK, RED } static class RBPrinter { public
static void visitNode(RBNode node) { RBNode n = if (n !=
null) System.out.print(n.key + "(" + (n.color == Color.RED ? "RED"
: "BLACK") + "),"); } }
static class RBNode&E extends
Comparable&E&& { E
RBNode&E& left,
RBNode(RBNode&E& p, E key, Color
color) { this.key = this.color = this.parent =
this.left = this.right = } }
private RBNode&E&
public RBTreeTest() { root = }
public boolean isEmpty() { return root == }
public E findMax() { if (isEmpty())
RBNode&E& node = while
((node.right) != null) { node = node. } return node.
public E findMin() { if (isEmpty())
RBNode&E& node = while
((node.left) != null) { node = node. } return node.
public final boolean contains(E ele) {
RBNode&E& tmp = int cmp = -1;
while (tmp != null) { cmp = pareTo(tmp.key); if (cmp
tmp = tmp. } else if (cmp & 0) { tmp =
tmp. } else { } } }
public final boolean delete(E ele) {
RBNode&E& if (root ==
null) cur = while (cur != null
&& (cmp = pareTo(cur.key))
!= 0) { if (cmp & 0) cur = cur. else cur =
cur. } if (cur == null) { } if ((cur.left) !=
null && (cur.right) != null) {
RBNode&E& prev = cur. while
((prev.right) != null) { prev = prev. } cur.key = prev.
cur = } if ((cur.left) != null) { if (cur == root) { root =
cur. root.color = Color.BLACK; } if
(cur.parent.left == cur) { cur.parent.left = cur.
cur.left.parent = cur. } else { cur.parent.right =
cur.left.parent = cur. } if (cur.color == Color.BLACK) {
cur.left.color = Color.BLACK; } } else if ((cur.right) != null) {
if (cur == root) { root = cur. root.color = Color.BLACK;
} if (cur.parent.left == cur) { cur.parent.left =
cur. cur.right.parent = cur. } else { cur.parent.right
= cur. cur.right.parent = cur. } if (cur.color ==
Color.BLACK) { cur.right.color = Color.BLACK; } } else { if (cur ==
root) { root = }
RBNode&E& if (cur.parent.left
== cur) { todo = cur.parent.left = } else { todo =
cur.parent.right = } if (cur.color == Color.BLACK) {
fixupDoubleBlack(todo); } } }
private final void
fixupDoubleBlack(RBNode&E& cur) {
while (cur != root) { p = cur. if (p.left == cur) { sibling
= p. if (sibling.color == Color.RED) { rotateLeft(p); p.color
= Color.RED; sibling.color = Color.BLACK; } else { if
(sibling.right.color == Color.RED) { rotateLeft(p); p.color =
Color.BLACK; sibling.right.color = Color.BLACK; } else if
(sibling.left.color == Color.RED) { rotateRight(sibling);
sibling.color = Color.RED; sibling.parent.color = Color.BLACK; }
else { sibling.color = Color.RED; if (p.color == Color.BLACK) { cur
= } else { p.color = Color.BLACK; } } } } else { sibling
= p. if (sibling.color == Color.RED) { rotateRight(p); p.color
= Color.RED; sibling.color = Color.BLACK; } else { if
(sibling.left.color == Color.RED) { rotateRight(p); sibling.color =
p. p.color = Color.BLACK; sibling.left.color = Color.BLACK;
} else if (sibling.right.color == Color.RED) {
rotateLeft(sibling); sibling.color = Color.RED;
sibling.parent.color = Color.BLACK; } else { sibling.color =
Color.RED; if (p.color == Color.BLACK) { cur = } else { p.color
= Color.BLACK; } } } } } }
public final void insert(E ele) { if (root == null) { // 添加根节点 root
= new RBNode&E&(null, ele,
Color.BLACK); } else { // 将该节点添加到合适的叶子节点的位置
RBNode&E& parent =
RBNode&E& cur = int cmp = -1;
while (cur != null && (cmp =
pareTo(cur.key)) != 0) { parent = if (cmp
& 0) cur = cur. else cur = cur. } if (cmp
== 0) { // 不能添加相同的元素 throw new IllegalArgumentException( "can't
insert duplicate key!"); } cur = new
RBNode&E&(parent, ele, Color.RED); if
(cmp & 0) { // 添加为左孩子 parent.left = } else { //
添加为右孩子 parent.right = }
insertFixup(cur); // 调整各个节点 } }
private final void
insertFixup(RBNode&E& cur) {
RBNode&E& p, while (cur != root
&& cur.color == Color.RED) { p =
cur. if (p.color == Color.BLACK) { } g = p.
if (p == g.left) { // p是g的左子树
RBNode&E& uncle = g. if (uncle
!= null && uncle.color ==
Color.RED) { g.color = Color.RED; uncle.color = p.color =
Color.BLACK; cur = } else { if (cur == p.right) { cur =
rotateLeft(p); cur = cur. } cur = rotateRight(g); cur.color =
Color.BLACK; cur.left.color = cur.right.color = Color.RED; } } else
{ // p是g的右子树 RBNode&E& uncle =
g. if (uncle != null &&
uncle.color == Color.RED) { g.color = Color.RED; uncle.color =
p.color = Color.BLACK; cur = } else { if (cur == p.left) { cur =
rotateRight(p); cur = cur. } cur = rotateLeft(g); cur.color =
Color.BLACK; cur.left.color = cur.right.color = Color.RED; } }
root.color = Color.BLACK; }
private final RBNode&E&
rotateLeft(RBNode&E& p) {
RBNode&E& gr = p.//grandfather
RBNode&E& ch = p. //children
p.right = ch. if (ch.left != null) { ch.left.parent = }
ch.left = p.parent = if (gr != null) { //p不是root节点 if
(gr.left == p) //如果p是gr的左孩子 gr.left = else //p是gr的右孩子 gr.right
= } else { //p是root节点 root = } ch.parent = }
private final RBNode&E&
rotateRight(RBNode&E& p) {
RBNode&E& gr = p.
RBNode&E& ch = p. p.left =
ch. if (ch.right != null) { ch.right.parent = } ch.right =
p; p.parent = if (gr != null) { if (gr.left == p) gr.left =
else gr.right = } else { root = } ch.parent = return
} public void inOrder(){ inOrder(root); } private void
inOrder(RBNode&E& cur) { if(cur !=
null){ inOrder(cur.left); RBPrinter.visitNode(cur);
inOrder(cur.right); } }
public static void main(String[] args) { java.util.Random ran = new
java.util.Random();
RBTreeTest&Integer& rbt = new
RBTreeTest&Integer&(); int tmp = 0;
for(int i=0;i&15;i++){ tmp = ran.nextInt(1000); try{
rbt.insert(tmp); } catch (IllegalArgumentException e){ do{
tmp = ran.nextInt(1000); }while(rbt.contains(tmp));
rbt.insert(tmp); } System.out.println(tmp); }
System.out.print("\nInorder begin:\n"); rbt.inOrder();
System.out.print("\nInorder end\n"); rbt.delete(tmp);
System.out.print("\nInorder begin:\n"); rbt.inOrder();
System.out.print("\nInorder end\n"); } }
1.堆排序定义 n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)： (1)
ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
2、大根堆和小根堆 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 注意：
①堆中任一子树亦是堆。 ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。 3、堆排序特点
堆排序(HeapSort)是一树形选择排序。
堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。
4、堆排序与直接插入排序的区别
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的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个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
（3）堆排序的算法： void HeapSort(SeqIAst R) { //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i； BuildHeap(R)； //将R[1-n]建成初始堆
for(i=n;i&1；i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换 Heapify(R，1，i-1)；
//将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 } //endfor } //HeapSort
（4） BuildHeap和Heapify函数的实现 因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。 ①
Heapify函数思想方法
每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。
"筛选法"调整堆
R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。
要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然只有一个结点的树是堆，而在完全二叉树中，所有序号的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为，
-1，…，1的结点作为根的子树都调整为堆即可。 具体算法【参见教材】。 5、算法分析
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。
十、带权图
带权图中，边带有一个数字，叫做权，它可能代表距离、耗费、时间或其他意义。
带权图用来最常解决的问题是最短路径问题（pps）。
带权图的最小生成树中有所有的顶点和连接它们的必要的边，且这些边的权值最小。
优先级队列的算法可用于寻找带权图的最小生成树。
解决无向带权图的最小生成树的方法
找到从最新的顶点到其他顶点的所有边，这些顶点不能在树的集合中，把这些边放如优先级队列。
找出权值最小的边，把它和它所到达的顶点放入树的集合中。
重复以上步骤，直到所有顶点都在树的集合中。
带权图的最短路径问题可以用Dijkstra算法解决。这个算法基于图的邻接矩阵表示法，它不仅能找到任意两点间的最短路径，还可以找到某个指定点到其他所有顶点的最短路径。
Dijkstra算法的思想：
以解决寻找一条从一个城市到另一个城市的费用最低的路线为例（假设不能直接指导所有路线的费用，只能直接知道到邻接城市的费用）
每次派一个代理人到新的城市，用这个代理人提供的新信息修正和完善费用清单，在表中之保留从源点到某个城市现在一直的最低费用
不断向某个新城市派代理人，条件是从源点到那个城市的路线费用最低。
有时为了看出某条路线是否可能，需要创建一个连通表。在带权图中，用一张表给出任意两个顶点间的最低耗费，这对顶点可能通过几条边相连。这种问题叫做每一对顶点之间的最短路径问题。Warshall算法（此算法在图章节中详述）能很快创建这样的连通表。
在带权图中类似的方法叫做Floyd算法。
Floyd算法与Warshall算法的区别。在Warshall算法中当找到一个两段路径时，只是简单的在表中插入1，在Floyd算法中，需要把两端的权值相加，并插入它们的和。
关于各种图的算法的效率：
图的表示法有两种：邻接矩阵和邻接表
算法 时间级
邻接矩阵（所有） O（V²）
无权邻接表 O(V + E)
带权邻接表 O((E+V)logV)
Warshall和Floyd算法 O（V³）
其中V是顶点数量，E是边的数量
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。