您的位置:

java常用算法,java常用算法和数据结构

本文目录一览:

数据结构 java开发中常用的排序算法有哪些

排序算法有很多,所以在特定情景中使用哪一种算法很重要。为了选择合适的算法,可以按照建议的顺序考虑以下标准:

(1)执行时间

(2)存储空间

(3)编程工作

对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要。

主要排序法有:

一、冒泡(Bubble)排序——相邻交换

二、选择排序——每次最小/大排在相应的位置

三、插入排序——将下一个插入已排好的序列中

四、壳(Shell)排序——缩小增量

五、归并排序

六、快速排序

七、堆排序

八、拓扑排序

一、冒泡(Bubble)排序

----------------------------------Code 从小到大排序n个数------------------------------------

void BubbleSortArray()

{

for(int i=1;in;i++)

{

for(int j=0;in-i;j++)

{

if(a[j]a[j+1])//比较交换相邻元素

{

int temp;

temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;

}

}

}

}

-------------------------------------------------Code------------------------------------------------

效率 O(n²),适用于排序小列表。

二、选择排序

----------------------------------Code 从小到大排序n个数--------------------------------

void SelectSortArray()

{

int min_index;

for(int i=0;in-1;i++)

{

min_index=i;

for(int j=i+1;jn;j++)//每次扫描选择最小项

if(arr[j]arr[min_index]) min_index=j;

if(min_index!=i)//找到最小项交换,即将这一项移到列表中的正确位置

{

int temp;

temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;

}

}

}

-------------------------------------------------Code-----------------------------------------

效率O(n²),适用于排序小的列表。

三、插入排序

--------------------------------------------Code 从小到大排序n个数-------------------------------------

void InsertSortArray()

{

for(int i=1;in;i++)//循环从第二个数组元素开始,因为arr[0]作为最初已排序部分

{

int temp=arr[i];//temp标记为未排序第一个元素

int j=i-1;

while (j=0 arr[j]temp)/*将temp与已排序元素从小到大比较,寻找temp应插入的位置*/

{

arr[j+1]=arr[j];

j--;

}

arr[j+1]=temp;

}

}

------------------------------Code--------------------------------------------------------------

最佳效率O(n);最糟效率O(n²)与冒泡、选择相同,适用于排序小列表

若列表基本有序,则插入排序比冒泡、选择更有效率。

四、壳(Shell)排序——缩小增量排序

-------------------------------------Code 从小到大排序n个数-------------------------------------

void ShellSortArray()

{

for(int incr=3;incr0;incr--)//增量递减,以增量3,2,1为例

{

for(int L=0;L(n-1)/incr;L++)//重复分成的每个子列表

{

for(int i=L+incr;in;i+=incr)//对每个子列表应用插入排序

{

int temp=arr[i];

int j=i-incr;

while(j=0arr[j]temp)

{

arr[j+incr]=arr[j];

j-=incr;

}

arr[j+incr]=temp;

}

}

}

}

--------------------------------------Code-------------------------------------------

适用于排序小列表。

效率估计O(nlog2^n)~O(n^1.5),取决于增量值的最初大小。建议使用质数作为增量值,因为如果增量值是2的幂,则在下一个通道中会再次比较相同的元素。

壳(Shell)排序改进了插入排序,减少了比较的次数。是不稳定的排序,因为排序过程中元素可能会前后跳跃。

五、归并排序

----------------------------------------------Code 从小到大排序---------------------------------------

void MergeSort(int low,int high)

{

if(low=high) return;//每个子列表中剩下一个元素时停止

else int mid=(low+high)/2;/*将列表划分成相等的两个子列表,若有奇数个元素,则在左边子列表大于右侧子列表*/

MergeSort(low,mid);//子列表进一步划分

MergeSort(mid+1,high);

int [] B=new int [high-low+1];//新建一个数组,用于存放归并的元素

for(int i=low,j=mid+1,k=low;i=mid j=high;k++)/*两个子列表进行排序归并,直到两个子列表中的一个结束*/

{

if (arr[i]=arr[j];)

{

B[k]=arr[i];

I++;

}

else

{ B[k]=arr[j]; j++; }

}

for( ;j=high;j++,k++)//如果第二个子列表中仍然有元素,则追加到新列表

B[k]=arr[j];

for( ;i=mid;i++,k++)//如果在第一个子列表中仍然有元素,则追加到新列表中

B[k]=arr[i];

for(int z=0;zhigh-low+1;z++)//将排序的数组B的 所有元素复制到原始数组arr中

arr[z]=B[z];

}

-----------------------------------------------------Code---------------------------------------------------

效率O(nlogn),归并的最佳、平均和最糟用例效率之间没有差异。

适用于排序大列表,基于分治法。

六、快速排序

------------------------------------Code--------------------------------------------

/*快速排序的算法思想:选定一个枢纽元素,对待排序序列进行分割,分割之后的序列一个部分小于枢纽元素,一个部分大于枢纽元素,再对这两个分割好的子序列进行上述的过程。*/ void swap(int a,int b){int t;t =a ;a =b ;b =t ;}

int Partition(int [] arr,int low,int high)

{

int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素

while (low high)

{

//从后往前栽后半部分中寻找第一个小于枢纽元素的元素

while (low high arr[high] = pivot)

{

--high;

}

//将这个比枢纽元素小的元素交换到前半部分

swap(arr[low], arr[high]);

//从前往后在前半部分中寻找第一个大于枢纽元素的元素

while (low high arr [low ]=pivot )

{

++low ;

}

swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分

}

return low ;//返回枢纽元素所在的位置

}

void QuickSort(int [] a,int low,int high)

{

if (low high )

{

int n=Partition (a ,low ,high );

QuickSort (a ,low ,n );

QuickSort (a ,n +1,high );

}

}

----------------------------------------Code-------------------------------------

平均效率O(nlogn),适用于排序大列表。

此算法的总时间取决于枢纽值的位置;选择第一个元素作为枢纽,可能导致O(n²)的最糟用例效率。若数基本有序,效率反而最差。选项中间值作为枢纽,效率是O(nlogn)。

基于分治法。

七、堆排序

最大堆:后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字,此时位于堆顶的节点的关键字是整个序列中最大的。

思想:

(1)令i=l,并令temp= kl ;

(2)计算i的左孩子j=2i+1;

(3)若j=n-1,则转(4),否则转(6);

(4)比较kj和kj+1,若kj+1kj,则令j=j+1,否则j不变;

(5)比较temp和kj,若kjtemp,则令ki等于kj,并令i=j,j=2i+1,并转(3),否则转(6)

(6)令ki等于temp,结束。

-----------------------------------------Code---------------------------

void HeapSort(SeqIAst R)

{ //对R[1..n]进行堆排序,不妨用R[0]做暂存单元 int I; BuildHeap(R); //将R[1-n]建成初始堆for(i=n;i1;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]可能违反堆性质 } } ---------------------------------------Code--------------------------------------

堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序,辅助空间为O(1), 它是不稳定的排序方法。

堆排序与直接插入排序的区别:

直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果,可减少比较次数。

八、拓扑排序

例 :学生选修课排课先后顺序

拓扑排序:把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。

方法:

在有向图中选一个没有前驱的顶点且输出

从图中删除该顶点和所有以它为尾的弧

重复上述两步,直至全部顶点均已输出(拓扑排序成功),或者当图中不存在无前驱的顶点(图中有回路)为止。

---------------------------------------Code--------------------------------------

void TopologicalSort()/*输出拓扑排序函数。若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR*/

{

int indegree[M];

int i,k,j;

char n;

int count=0;

Stack thestack;

FindInDegree(G,indegree);//对各顶点求入度indegree[0....num]

InitStack(thestack);//初始化栈

for(i=0;iG.num;i++)

Console.WriteLine("结点"+G.vertices[i].data+"的入度为"+indegree[i]);

for(i=0;iG.num;i++)

{

if(indegree[i]==0)

Push(thestack.vertices[i]);

}

Console.Write("拓扑排序输出顺序为:");

while(thestack.Peek()!=null)

{

Pop(thestack.Peek());

j=locatevex(G,n);

if (j==-2)

{

Console.WriteLine("发生错误,程序结束。");

exit();

}

Console.Write(G.vertices[j].data);

count++;

for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)

{

k=p.adjvex;

if (!(--indegree[k]))

Push(G.vertices[k]);

}

}

if (countG.num)

Cosole.WriteLine("该图有环,出现错误,无法排序。");

else

Console.WriteLine("排序成功。");

}

----------------------------------------Code--------------------------------------

算法的时间复杂度O(n+e)。

java实现几种常见排序算法

下面给你介绍四种常用排序算法:

1、冒泡排序

特点:效率低,实现简单

思想(从小到大排):每一趟将待排序序列中最大元素移到最后,剩下的为新的待排序序列,重复上述步骤直到排完所有元素。这只是冒泡排序的一种,当然也可以从后往前排。

2、选择排序

特点:效率低,容易实现。

思想:每一趟从待排序序列选择一个最小的元素放到已排好序序列的末尾,剩下的位待排序序列,重复上述步骤直到完成排序。

3、插入排序

特点:效率低,容易实现。

思想:将数组分为两部分,将后部分元素逐一与前部分元素比较,如果当前元素array[i]小,就替换。找到合理位置插入array[i]

4、快速排序

特点:高效,时间复杂度为nlogn。

采用分治法的思想:首先设置一个轴值pivot,然后以这个轴值为划分基准将待排序序列分成比pivot大和比pivot小的两部分,接下来对划分完的子序列进行快排直到子序列为一个元素为止。

java中的算法,一共有多少种,哪几种,怎么分类。

就好比问,汉语中常用写作方法有多少种,怎么分类。

算法按用途分,体现设计目的、有什么特点

算法按实现方式分,有递归、迭代、平行、序列、过程、确定、不确定等等

算法按设计范型分,有分治、动态、贪心、线性、图论、简化等等

作为图灵完备的语言,理论上”Java语言“可以实现所有算法。

“Java的标准库'中用了一些常用数据结构和相关算法.

像apache common这样的java库中又提供了一些通用的算法

java最常用的几种加密算法

简单的Java加密算法有:

第一种. BASE

Base是网络上最常见的用于传输Bit字节代码的编码方式之一,大家可以查看RFC~RFC,上面有MIME的详细规范。Base编码可用于在HTTP环境下传递较长的标识信息。例如,在Java Persistence系统Hibernate中,就采用了Base来将一个较长的唯一标识符(一般为-bit的UUID)编码为一个字符串,用作HTTP表单和HTTP GET URL中的参数。在其他应用程序中,也常常需要把二进制数据编码为适合放在URL(包括隐藏表单域)中的形式。此时,采用Base编码具有不可读性,即所编码的数据不会被人用肉眼所直接看到。

第二种. MD

MD即Message-Digest Algorithm (信息-摘要算法),用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一(又译摘要算法、哈希算法),主流编程语言普遍已有MD实现。将数据(如汉字)运算为另一固定长度值,是杂凑算法的基础原理,MD的前身有MD、MD和MD。

MD算法具有以下特点:

压缩性:任意长度的数据,算出的MD值长度都是固定的。

容易计算:从原数据计算出MD值很容易。

抗修改性:对原数据进行任何改动,哪怕只修改个字节,所得到的MD值都有很大区别。

弱抗碰撞:已知原数据和其MD值,想找到一个具有相同MD值的数据(即伪造数据)是非常困难的。

强抗碰撞:想找到两个不同的数据,使它们具有相同的MD值,是非常困难的。

MD的作用是让大容量信息在用数字签名软件签署私人密钥前被”压缩”成一种保密的格式(就是把一个任意长度的字节串变换成一定长的十六进制数字串)。除了MD以外,其中比较有名的还有sha-、RIPEMD以及Haval等。

第三种.SHA

安全哈希算法(Secure Hash Algorithm)主要适用于数字签名标准(Digital Signature Standard DSS)里面定义的数字签名算法(Digital Signature Algorithm DSA)。对于长度小于^位的消息,SHA会产生一个位的消息摘要。该算法经过加密专家多年来的发展和改进已日益完善,并被广泛使用。该算法的思想是接收一段明文,然后以一种不可逆的方式将它转换成一段(通常更小)密文,也可以简单的理解为取一串输入码(称为预映射或信息),并把它们转化为长度较短、位数固定的输出序列即散列值(也称为信息摘要或信息认证代码)的过程。散列函数值可以说是对明文的一种“指纹”或是“摘要”所以对散列值的数字签名就可以视为对此明文的数字签名。

SHA-与MD的比较

因为二者均由MD导出,SHA-和MD彼此很相似。相应的,他们的强度和其他特性也是相似,但还有以下几点不同:

对强行攻击的安全性:最显著和最重要的区别是SHA-摘要比MD摘要长 位。使用强行技术,产生任何一个报文使其摘要等于给定报摘要的难度对MD是^数量级的操作,而对SHA-则是^数量级的操作。这样,SHA-对强行攻击有更大的强度。

对密码分析的安全性:由于MD的设计,易受密码分析的攻击,SHA-显得不易受这样的攻击。

速度:在相同的硬件上,SHA-的运行速度比MD慢。

第四种.HMAC

HMAC(Hash Message Authentication Code,散列消息鉴别码,基于密钥的Hash算法的认证协议。消息鉴别码实现鉴别的原理是,用公开函数和密钥产生一个固定长度的值作为认证标识,用这个标识鉴别消息的完整性。使用一个密钥生成一个固定大小的小数据块,即MAC,并将其加入到消息中,然后传输。接收方利用与发送方共享的密钥进行鉴别认证等。

java常见gc算法有哪些

1:标记—清除

Mark-Sweep

过程:标记可回收对象,进行清除

缺点:标记和清除效率低,清除后会产生内存碎片

2:复制算法

过程:将内存划分为相等的两块,将存活的对象复制到另一块内存,把已经使用的内存清理掉

缺点:使用的内存变为了原来的一半

进化:将一块内存按8:1的比例分为一块Eden区(80%)和两块Survivor区(10%)

每次使用Eden和一块Survivor,回收时,将存活的对象一次性复制到另一块Survivor上,如果另一块Survivor空间不足,则使用分配担保机制存入老年代

3:标记—整理

Mark—Compact

过程:所有存活的对象向一端移动,然后清除掉边界以外的内存

4:分代收集算法

过程:将堆分为新生代和老年代,根据区域特点选用不同的收集算法,如果新生代朝生夕死,则采用复制算法,老年代采用标记清除,或标记整理

面试的话说出来这四种足够了