- 相关推荐
Java常用的五大排序算法
排序算法的使用可以让我们更方便的进行排序，下面是小编给大家提供的Java常用的五大排序算法，大家可以参考阅读。
Java的五大排序算法1
1、Java排序算法之选择排序
选择排序的基本思想是遍历数组的过程中，以i代表当前需要排序的序号，则需要在剩余的[i…n-1]中找出其中的最小值，然后将找到的最小值与i指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。
举个实例来看看：
1.初始：[38,17,16,16,7,31,39,32,2,11]
2.3.i=0:[2，17,16,16,7,31,39,32,38，11](0th[38]<->8th[2])
6.7.i=2:[2,7,11，16,17,31,39,32,38,16](2nd[11]<->9th[16])
12.13.i=5:[2,7,11,16,16,17，39,32,38,31](5th[31]<->9th[17])
16.17.i=7:[2,7,11,16,16,17,31,32,38,39](无需交换)
18.19.i=8:[2,7,11,16,16,17,31,32,38,39](无需交换)
20.21.i=9:[2,7,11,16,16,17,31,32,38,39](无需交换)
由例子可以看出，选择排序随着排序的进行(i逐渐增大)，比较的次数会越来越少，但是不论数组初始是否有序，选择排序都会从i至数组末尾进行一次选择比较，所以给定长度的数组，选择排序的比较次数是固定的：1+2+3+…+n=nx(n+1)/2，而交换的次数则跟初始数组的顺序有关，如果初始数组顺序为随机，则在最坏情况下，数组元素将会交换n次，最好的情况下则可能0次(数组本身即为有序)。
由此可以推出，选择排序的时间复杂度和空间复杂度分别为O(n2)和O(1)(选择排序只需要一个额外空间用于数组元素交换)。
实现代码：
1./xx
2.xSelectionSorting
3.x/
4.SELECTION(newSortable(){
5.public
6.intlen=array.length;
7.for(inti=0;i<len;i++){
8.intselected=i;
9.for(intj=i+1;j<len;j++){
10.intcompare=array[j].compareTo(array[selected]);
11.if(compare!=0&&compare<0==ascend){
12.selected=j;
13.}
14.}
15.16.exchange(array,i,selected);
17.}
18.}
19.})
2、Java排序算法之插入排序
插入排序的基本思想是在遍历数组的过程中，假设在序号i之前的元素即[0i-1]都已经排好序，本趟需要找到i对应的元素x的正确位置k，并且在寻找这个位置k的过程中逐个将比较过的元素往后移一位，为元素x"腾位置",最后将k对应的元素值赋为x，插入排序也是根据排序的特性来命名的。
以下是一个实例，红色标记的数字为插入的数字，被划掉的数字是未参与此次排序的元素，红色标记的数字与被划掉数字之间的元素为逐个向后移动的元素，比如第二趟参与排序的元素为[11,31,12]，需要插入的元素为12，但是12当前并没有处于正确的位置，于是我们需要依次与前面的元素31、11做比较，一边比较一边移动比较过的元素，直到找到第一个比12小的元素11时停止比较，此时31对应的索引1则是12需要插入的位置。
3、Java排序算法之冒泡排序
冒泡排序可以算是最经典的排序算法了，记得小弟上学时最先接触的也就是这个算法了，因为实现方法最简单，两层for循环，里层循环中判断相邻两个元素是否逆序，是的话将两个元素交换，外层循环一次，就能将数组中剩下的元素中最小的元素"浮"到最前面，所以称之为冒泡排序。
其实冒泡排序跟选择排序比较相像，比较次数一样，都为nx(n+1)/2，但是冒泡排序在挑选最小值的过程中会进行额外的交换(冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换，与之对应的是选择排序，只会在内层循环比较结束之后根据情况决定是否进行交换)，所以在我看来，选择排序属于冒泡排序的改进版。
4、Java排序算法之希尔排序
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组"分而治之",划分为若干个小的数组，以gap来划分，比如数组[1,2,3,4,5,6,7,8]，如果以gap=2来划分，可以分为[1,3,5,7]和[2,4,6,8]两个数组(对应的，如gap=3，则划分的数组为：[1,4,7]、[2,5,8]、[3,6])然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小gap值重复进行之前的步骤，直至gap=1，即对整个数组进行插入排序，此时的数组已经基本上快排好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题。
具体实例请参照插入排序。
希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。
5、Java排序算法之归并排序
归并排序采用的是递归来实现，属于"分而治之",将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组"归并"到一起，归并排序最重要的.也就是这个"归并"的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间，比如需要规定的数组分别为：[3,6,8,11]和[1,3,12,15](虽然逻辑上被划为为两个数组，但实际上这些元素还是位于原来数组中的，只是通过一些index将其划分成两个数组，原数组为[3,6,8,11,1,3,12,15，我们设置三个指针lo,mid,high分别为0,3,7就可以实现逻辑上的子数组划分)那么需要的额外数组的长度为4+4=8.归并的过程可以简要地概括为如下：
1)将两个子数组中的元素复制到新数组copiedArray中，以前面提到的例子为例，则copiedArray=[3,6,8,11,1,3,12,15];
2)设置两个指针分别指向原子数组中对应的第一个元素，假定这两个指针取名为leftIdx和rightIdx，则leftIdx=0(对应copiedArray中的第一个元素[3])，rightIdx=4(对应copiedArray中的第五个元素[1]);
3)比较leftIdx和rightIdx指向的数组元素值，选取其中较小的一个并将其值赋给原数组中对应的位置i，赋值完毕后分别对参与赋值的这两个索引做自增1操作，如果leftIdx或rigthIdx值已经达到对应数组的末尾，则余下只需要将剩下数组的元素按顺序copy到余下的位置即可。
下面给个归并的具体实例：
1.第一趟：
2.3.辅助数组[21，28,39|35,38](数组被拆分为左右两个子数组，以|分隔开)
4.5.[21，，，，](第一次21与35比较，左边子数组胜出，leftIdx=0，i=0)
6.7.第二趟：
8.9.辅助数组[21,28，39|35,38]
10.11.[21，28,，，](第二次28与35比较，左边子数组胜出，leftIdx=1，i=1)
12.13.第三趟：[21,28,39|35，38]
14.15.[21，28，35,，](第三次39与35比较，右边子数组胜出，rightIdx=0，i=2)
16.17.第四趟：[21,28,39|35,38]
18.19.[21，28，35，38,](第四次39与38比较，右边子数组胜出，rightIdx=1，i=3)
20.21.第五趟：[21,28,39|35,38]
22.23.[21，28，35，38，39](第五次时右边子数组已复制完，无需比较leftIdx=2，i=4)
以上便是一次归并的过程，我们可以将整个需要排序的数组做有限次拆分(每次一分为二)直到分为长度为1的小数组为止，长度为1时数组已经不用排序了。在这之后再逆序(由于采用递归)依次对这些数组进行归并操作，直到最后一次归并长度为n/2的子数组，归并完成之后数组排序也完成。
归并排序需要的额外空间是所有排序中最多的，每次归并需要与参与归并的两个数组长度之和相同个元素(为了提供辅助数组)。则可以推断归并排序的空间复杂度为1+2+4+…+n=nx(n+2)/4(忽略了n的奇偶性的判断)，时间复杂度比较难估，这里小弟也忘记是多少了(囧)。
Java的五大排序算法2
简单选择排序：
（选出最小值，放在第一位，然后第一位向后推移，如此循环）第一位与后面每一个逐个比较，每次都使最小的置顶，第一位向后推进（即刚选定的第一位是最小值，不再参与比较，比较次数减1）
复杂度：所需进行记录移动的操作次数较少0--3(n-1)，无论记录的初始排列如何，所需的关键字间的比较次数相同，均为n(n-1)/2，总的时间复杂度为O(n2)；
空间复杂度O(1)
算法改进：每次对比，都是为了将最小的值放到第一位，所以可以一比到底，找出最小值，直接放到第一位，省去无意义的调换移动操作。也可以换一个方向，最后一位与前面每一个比较，每次使最大值沉底，最后一位向前推进。
复制代码代码如下:
publicstaticvoidselectSort(Date[]days){
intmin;
Datetemp;
for(inti=0;i<days.length;i++){
min=i;
for(intj=min+1;j<days.length;j++){
if(days[min].compare(days[j])>0){
min=j;
}
}
if(min!=i){
temp=days[i];
days[i]=days[min];
days[min]=temp;
}
}
}
classDate{
intyear,month,day;
Date(inty,intm,intd){
year=y;
month=m;
day=d;
}
publicintcompare(Datedate){
returnyear>date.year?1:year<date.year?-1
:month>date.month?1:month<date.month?-1
:day>date.day?1:day<date.day?-1:0;
}
publicvoidprint(){
System.out.println(year+""+month+""+day);
}
}
简单选择排序（SimpleSelectionSort）：
简单选择排序类似于冒泡排序（BubbleSort），每次都会在剩下的元素集合中选择出一个最值出来填充到当前位置。唯一的区别是，冒泡排序在每次发现比当前值小于（或大于）时，都会交换元素的位置，而简单选择排序是选择剩余元素中的最值和当前位置交换数据。
比如对于元素集合R={37,40,38,42,461,5,7,9,12}
在第一趟排序中：37直接和5交换，形成新的序列R1={5,40,38,42,461,37,7,9,12}
在第二趟排序中：40直接和7交换，形成新的序列R2={5,7,38,42,461,37,40,9,12}
以此类推，直到最后一个元素（注意：在第二趟排序中，38比42小，但是他们并没有交换数据）。
以下是简单选择排序的一个Java实现版本：
复制代码代码如下:
publicstaticvoidselectionSort（int[]data）{
if（data==null||data.length<=1）
return;
inti,j,value,minPos,len=data.length;
intouter=len-1,tmp;
for（i=0;i<outer;i++）{
value=data[i];
minPos=-1;
for（j=i+1;j<len;j++）{
if（data[j]<value）{
minPos=j;
value=data[j];
}
}
if（minPos!=-1）{
tmp=data[i];
data[i]=value;
data[minPos]=tmp;
}
//for（intk=0;k<len;k++）{
//System.out.print（data[k]+"，"）；
//}
//System.out.println（）；
}
}
publicstaticvoidmain（String[]args）{
int[]coll={
37,40,38,42,461,5,7,9,12
};
selectionSort（coll）；
for（inti=0;i<coll.length;i++）{
System.out.print（coll[i]+"，"）；
}
}
树选择排序（TreeSelectionSort）
树选择排序算法相对于简单选择排序来说是典型的'以空间换时间的算法。其思想是对待排序的N个元素，构造出相对较小的（n+1）/2个数，然后再构造出相对较小的[n+1]/4个数，直到只有一个元素为止。构造成一个完全二叉树。
排序的时候，那个元素就是最小的，取出该最小元素，将该元素替换为"最大值",再调整完全二叉树。
下面是树形选择排序的一个Java实现版：
复制代码代码如下:
publicstaticvoidtreeSelectionSort（int[]data）{
if（data==null||data.length<=1）
return;
intlen=data.length，low=0，i，j;
//addAuxiliarySpace
int[]tmp=newint[2xlen-1];
inttSize=tmp.length;
//constructatree
for（i=len-1，j=tmp.length-1;i>=0;i--,j--）{
tmp[j]=data[i];
}
for（i=tSize-1;i>0;i-=2）{
tmp[（i-1）/2]=tmp[i]>tmp[i-1]?tmp[i-1]:tmp[i];
}
//end
//removetheminimumnode.
while（low<len）{
data[low++]=tmp[0];
for（j=tSize-1;tmp[j]!=tmp[0];j--）；
tmp[j]=Integer.MAX_VALUE;
while（j>0）{
if（j%2==0）{//如果是右节点
tmp[（j-1）/2]=tmp[j]>tmp[j-1]?tmp[j-1]:tmp[j];
j=（j-1）/2;
}else{//如果是左节点
tmp[j/2]=tmp[j]>tmp[j+1]?tmp[j+1]:tmp[j];
j=j/2;
}
}
}
}
在构造完全二叉树的时候对N个元素的集合，需要2xN-1个辅助空间。
复制代码代码如下:
while（j>0）{
if（j%2==0）{//如果是右节点
tmp[（j-1）/2]=tmp[j]>tmp[j-1]?tmp[j-1]:tmp[j];
j=（j-1）/2;
}else{//如果是左节点
tmp[j/2]=tmp[j]>tmp[j+1]?tmp[j+1]:tmp[j];
j=j/2;
}
}
则实现递归的构造新集合中的最小值。
【Java的五大排序算法】相关文章：
什么是Java10-28
《算法及其实现》的备课教案08-25
java类的构成04-28
Excel表格怎么自动排序10-14
小班数学排序教案10-18
中班数学排序教案11-23
Java基础知识精选02-20
新手如何学习Java07-06
Java语言的内部类12-13