本文目录一览:
数据结构 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开发,一般需要学多久呀?
我们大家学习Java从入门到能掌握可以找到一份工作,平均周期在三年左右,也有一些两年就自学完成的,而且我个人认为报培训班是很需要的,我们大家在刚接触Java的时候,会有些迷茫,不知道该从哪里入手,那是因为在学习上没找到对的方法。
学习是场持久战,短时间的突击学习收获并不是很大,学习重在行动、贵在坚持,能坚持下来才是最难能可贵的。
学习java,说实话,入门并不难,但是学精可不容易!对于零基础学习java编程所需要的时间也是受很多因素影响的,比如,你自身的学历,学习态度,是自学还是培训等,所以无法用一个确定的时间段来进行评估。
对于零基础的学生来说,想学好java编程,参加专业的软件编程培训是很有必要的。专业的软件学校都是因材施教,针对不同的人群开设不同的班级,学的时间也有所不同,一般情况下,高中生是两年时间,大学生是6个月左右的学习时间。
如果是自学的话,自学的话比较考验你的学习能力与自律能力,想要熟练掌握Java技术,至少需要两年左右的时间(高中生的话那时间会更长)!不过也有学得快的,建议您如果自学的话,可以采纳!
1、找一个行业当中的师傅进行规划和指导。
2、每天规划好学习时间,不要中断。
3、先掌握了解知识体系后编写项目,边抓细节。
java应用广泛,课程体系全面,零基础通过自学Java最终找到一份Java开发的工作,其实这件事还是有难度的。没有好的学习教材以及良性的学习规划、遇到难题无法解决导致学习效率很低、作为一个零基础的初学者没有人指导带着学都是需要克服的问题。
培训的话,一般培训机构会根据课程安排及大纲进行教学,通过6个月左右的时间,就能掌握Java编程技术,将所学与项目结合,迈出程序员职业道路的第一步,随着工作经验的积累,薪资只会增长。
记住,学java还要看兴趣,如果你真的深入学习,你会发现“ 学java要多久 ?”是个毫无意义的问题,不要忘记,技术的道路更新实在太快。人只有在不断学习,才能走在技术的最前端。也许一辈子都要学呢?活到老,学到老,而且互联网技术更新迭代很快,只有不断学习才能更上时代不被淘汰。
学习Java开发都需要学些什么内容?
互联网行业目前还是最热门的行业之一,许多想入行互联网的人都会选择Java学习,发展前景非常好,普通人也可以学习。
如果想达到工作标准可以参考下面的内容:
1.Java SE部分 初级语法,面向对象,异常,IO流,多线程,Java Swing,JDBC,泛型,注解,反射等。
2.数据库部分,基础的sql语句,sql语句调优,索引,数据库引擎,存储过程,触发器,事务等。
3. 前端部分, HTML5 CSS3 JS, HTML DOM Jquery BootStrap等。
4. Java EE部分,Tomcat和Nginx服务器搭建,配置文件,Servlet,JSP,Filter,Listener,http协议,MVC等。
5. 框架部分,每个框架都可以分开学,在去学如何使用SSM 或者SSH框架,如何搭建,如何整合。开发中为什么会用框架,Rest是啥?Spring为啥经久不衰,底层如何实现等。
6.23种设计模式,掌握常用的,比如单例模式的多种实现,责任链模式,工厂模式,装饰器模式等,了解常用场景。
7. 基础算法和数据结构,八大排序算法,查找算法。
8. 熟练使用maven等构建工具,git等版本控制工具,熟悉常用linux命令,log4j,dubug,junit单元测试,日志打印工具,Redis等NoSql。
想要系统学习,你可以考察对比一下开设有相关专业的热门学校,好的学校拥有根据当下企业需求自主研发课程的能力,能够在校期间取得大专或本科学历,中博软件学院、南京课工场、南京北大青鸟等开设相关专业的学校都是不错的,建议实地考察对比一下。
祝你学有所成,望采纳。