04Java数据结构Word格式文档下载.docx
《04Java数据结构Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《04Java数据结构Word格式文档下载.docx(17页珍藏版)》请在冰点文库上搜索。
k<
100;
k++)
a++;
}
前后两次获得当前系统时间的差值就是运行所消耗的时间(毫秒为单位)。
通过System.currentTimeMillis()方法来测试的缺点:
a.不同的平台执行的时间不同
b.有些算法随着输入数据的加大,测试时间会变得不切实际!
4.2查找
4.2.1查找之线性查找(直接查找)
算法思路:
从数组的第一个元素开始查找,并将其与查找值比较,如果相等则停止,否则继续下一个元素查找,直到找到匹配值。
注意:
被查找的数组中的元素可以是无序的、随机的。
实例:
importjava.util.*;
publicclassDemo1
intiArr[]={32,9,78,44,29,18,97,49,56,61};
System.out.println("
数组的所有元素为:
"
);
for(inti:
iArr)
System.out.print(i+"
"
System.out.println();
System.out.print("
请输入你要查找的元素:
Scannerscan=newScanner(System.in);
intiNum=scan.nextInt();
intindex=straightSearch(iArr,iNum);
if(index==-1)
System.out.println("
没有找到元素"
+iNum);
else
找到元素"
+iNum+"
下标为:
+index);
publicstaticintstraightSearch(int[]arr,intnum)
inti=0;
for(;
arr.length;
{
if(arr[i]==num)
returni;
}
return-1;
4.2.2查找之折半查找(二分查找)
算法思路:
假设被查找数组中的元素是升序排列的,那我们查找值时,首先会直接到数组的中间位置(数组长度/2),并将中间值和查找值比较,如果相等则返回,否则,如果当前元素值小于查找值,则继续在数组的后面一半查找(重复上面过程);
如果当前元素值大于查找值,则继续在数组的前面一半查找,直到找到目标值或者无法再二分数组时停止。
二分查找只是针对有序排列的各种数组或集合。
//不利用递归实现
intiArr[]={1,2,3,4,6,8,22,44,99,111,112,116};
intindex=binarySearch(iArr,iNum,0,iArr.length-1);
publicstaticintbinarySearch(int[]arr,intnum,intiMin,intiMax)
while(iMin<
=iMax)
intiMid=(iMin+iMax)/2;
if(num==arr[iMid])
returniMid;
elseif(num<
arr[iMid])
iMax=iMid-1;
else
iMin=iMid+1;
//利用递归实现
intiMid=(iMin+iMax)/2;
if(num<
arr[iMin]||num>
arr[iMax])
return-1;
elseif(num==arr[iMid])
returniMid;
elseif(num<
returnbinarySearch(arr,num,iMin,iMid-1);
returnbinarySearch(arr,num,iMid+1,iMax);
4.3排序
4.3.1排序之插入排序
4.3.1.1插入排序之直接插入排序
直接插入排序(straightinsertionsort)是一种最简单的排序方法。
它的基本操作是将一个记录插入到一个长度为m(假设)的有序表中,使之仍保持有序,从而得到一个新的长度为m+1的有序表。
设有一组关键字{K1,K2,…,Kn};
排序开始就认为K1是一个有序序列;
让K2插入上述表长为1的有序序列,使之成为一个表长为2的有序序列;
然后让K3插入上述表长为2的有序序列,使之成为一个表长为3的有序序列;
依次类推,最后让Kn插入上述表长为n-1的有序序列,得一个表长为n的有序序列。
//49,38,65,97,76,13,27初始情况
//[49],38,65,97,76,13,27从下标1开始
//[38,49],65,97,76,13,27
//[38,49,65],97,76,13,27
//[38,49,65,97],76,13,27
//[38,49,65,76,97],13,27
//[13,38,49,65,76,97],27
//[13,27,38,49,65,76,97]
代码实现:
publicstaticvoidmain(String[]args){
inta[]={49,38,65,97,76,13,27};
straightInsertSort(a);
for(inti=0;
a.length;
System.out.print(a[i]+"
publicstaticvoidstraightInsertSort(inta[]){
inti,m;
for(i=1;
i++)//共进行n-1趟插入
m=i;
while(m>
=1&
&
a[m]<
a[m-1])//短路表达式
{
a[m]=(a[m]+a[m-1])-(a[m-1]=a[m]);
//比前一个小,则与之交换
m--;
}
4.3.1.2插入排序之折半插入排序
折半插入排序(Binaryinsertionsort)当直接插入排序进行到某一趟时,对于a[i]来讲,前边i-1个记录已经按有序。
此时不用直接插入排序的方法,而改为先用折半查找法找出r[i]应插的位置,然后再插入。
这种方法就是折半插入排序。
基本步骤:
a、初始化:
设定有序区为第一个元素,设定无序区为后面所有元素
b、依次取无序区的每个元素
c、通过二分法查找有序区,返回比这个数小的最大数
d、保留此位置数据
e、从此位置的元素到有序区的最后一个元素,依次后移
f、用保留的数据填充此位置
代码实现:
publicclassTest
binaryInsertSort(a);
publicstaticvoidbinaryInsertSort(inta[]){
for(inti=1;
intiTmp=a[i];
//将待插入数据临时保存到iTmp中去.
intm=findPosition(a,a[i],0,i-1);
//m是a[i]应该呆的位置
for(intj=i;
j>
m;
j--)
a[j]=a[j-1];
//整体向后移动一个位置
a[m]=iTmp;
//m是a[i]应该呆的位置
publicstaticintfindPosition(inta[],intnum,intiMin,intiMax)
a[iMin])
returniMin;
//超出范围,直接返回
if(num>
a[iMax])
returniMax+1;
//选取中值,准备二分
if(a[iMid]>
=num)//继续二分:
递归
returnfindPosition(a,num,iMin,iMid-1);
//目标在左边,递归左边(p[m]已经比较过,排出查找范围)
else//if(a[m]<
num)
returnfindPosition(a,num,iMid+1,iMax);
//目标在右边,递归右边(p[m]已经比较过,排出查找范围)
4.3.1.3插入排序之希尔排序
希尔排序(ShellSort):
是插入排序的一种。
因D.L.Shell于1959年提出而得名。
先取一个小于数组长度n的整数d1(一般为n/2)作为第一个增量,把文件的全部记录分成d1个组。
所有距离为dl的倍数的记录放在同一个组中。
先在各组内进行直接插入排序;
然后,取第二个增量d2<
d1(一般为d1/2),重复上述的分组和排序,直至所取的增量dt=1(dt<
dt-l<
…<
d2<
d1),即所有记录放在同一组中进行直接插入排序为止。
shellSort(a);
publicstaticvoidshellSort(inta[]){
intk=a.length/2;
//k值代表前文中的增量d值
while(k>
=1)//当增量k值变化到0,结束循环
for(inti=0;
k;
i++)//将数组分成k组,然后对每组进行直接插入排序.
for(intj=i+k;
j+=k)//共进行?
趟插入
{
intm=j;
while(m>
=k&
a[m-k])//短路表达式
{
a[m]=(a[m]+a[m-k])-(a[m-k]=a[m]);
m-=k;
}
}
k=k/2;
4.3.2排序之选择排序
4.3.2.1选择排序之直接选择排序
简单选择排序(simpleselectionsort)也是直接选择排序。
是一种较为容易理解的方法。
对于一组关键字{K1,K2,…,Kn},首先从K1,K2,…,Kn中选择最小值,假如它是Kz,则将Kz与K1对换;
然后从K2,K3,…,Kn中选择最小值Kz,再将Kz与K2对换。
如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1、Kn中选择最小值Kz将Kz与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成。
simpleSelectSort(a);
publicstaticvoidsimpleSelectSort(inta[]){
for(inti=1;
intiMax=0;
for(intj=1;
=a.length-i;
if(a[j]>
iMax=j;
if(iMax!
=a.length-i)
a[iMax]=(a[iMax]+a[a.length-i])-(a[a.length-i]=a[iMax]);
4.3.3排序之交换排序
4.3.3.1交换排序之冒泡排序
依次比较相邻的两个数,将小数放在前面,大数放在后面。
即在第一趟:
首先比较第1个和第2个数,将小数放前,大数放后。
然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。
至此第一趟结束,将最大的数放到了最后。
在第二趟:
仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。
如此下去,重复以上过程,直至最终完成排序。
在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。
bubbleSort(a);
publicstaticvoidbubbleSort(inta[]){
a.length-i;
a[j+1])
a[j]=(a[j]+a[j+1])-(a[j+1]=a[j]);
4.3.3.2交换排序之双向冒泡排序
是冒泡排序的升级。
双向冒泡是一个大泡从头往后冒,一个小泡从后往前冒。
相对冒泡排序可减少时间。
doubleBubbleSort(a);
publicstaticvoiddoubleBubbleSort(inta[]){
intn=a.length;
=n/2;
for(intj=i-1;
n-i;
if(a[n-1-j]<
a[n-2-j])
a[n-1-j]=(a[n-1-j]+a[n-2-j])-(a[n-2-j]=a[n-1-j]);
4.3.3.3交换排序之快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。
由C.A.R.Hoare在1962年提出。
它的基本思想是:
通过"
一趟排序"
将要排序的数据分割成独立的两部分,其中左部分的所有数据都比右部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
算法过程:
设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:
i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
注意该key值在整个过程中永远不变,始终是和key进行比较。
3)从j开始由后向前搜索,找到第一个小于key的值A[j],并与A[i]交换;
4)从i开始由前向后搜索,找到第一个大于key的值A[i],并与A[j]交换;
5)重复第3、4步,直到i=j;
注意:
3)和4)步是在程序中没找到时候才j--和i++,直至找到为止。
找到并交换的时候i和j指针位置不变。
值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快排演示:
key=49
49i386597761327j先找j开始,发现27比key小,交换i、j的值
27i386597761349j再从i开始,发现27和38都比key小,即i++
273849i97761365j直到i对应的值比key大,则i、j交换
273813i977649j65以此类推
27381349i7697j65
27381349ij769765
代码实现:
publicst