- 相關推薦
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的五大排序算法】相關文章：
Java排序算法06-17
java常見的排序算法的代碼09-20
常用Java排序算法詳解09-17
JAVA語言的常見排序算法07-16
java堆排序的算法思想的分析09-14
Java常用的7大排序算法08-30
JAVA簡單選擇排序算法及實現10-02
冒泡排序算法原理及JAVA實現代碼方法10-16
c語言的排序算法07-22