- 相關推薦
Java常用的五大排序算法
排序算法的使用可以讓我們更方便的進行排序，下面是小編給大家提供的Java常用的五大排序算法，大家可以參考閱讀。
Java的五大排序算法1
1、Java排序算法之選擇排序
選擇排序的基本思想是遍歷數(shù)組的過程中，以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逐漸增大)，比較的次數(shù)會越來越少，但是不論數(shù)組初始是否有序，選擇排序都會從i至數(shù)組末尾進行一次選擇比較，所以給定長度的數(shù)組，選擇排序的比較次數(shù)是固定的：1+2+3+…+n=nx(n+1)/2，而交換的次數(shù)則跟初始數(shù)組的順序有關，如果初始數(shù)組順序為隨機，則在最壞情況下，數(shù)組元素將會交換n次，最好的情況下則可能0次(數(shù)組本身即為有序)。
由此可以推出，選擇排序的時間復雜度和空間復雜度分別為O(n2)和O(1)(選擇排序只需要一個額外空間用于數(shù)組元素交換)。
實現(xiàn)代碼：
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排序算法之插入排序
插入排序的基本思想是在遍歷數(shù)組的過程中，假設在序號i之前的元素即[0i-1]都已經(jīng)排好序，本趟需要找到i對應的元素x的正確位置k，并且在尋找這個位置k的過程中逐個將比較過的元素往后移一位，為元素x"騰位置",最后將k對應的元素值賦為x，插入排序也是根據(jù)排序的特性來命名的。
以下是一個實例，紅色標記的數(shù)字為插入的數(shù)字，被劃掉的數(shù)字是未參與此次排序的元素，紅色標記的數(shù)字與被劃掉數(shù)字之間的元素為逐個向后移動的元素，比如第二趟參與排序的元素為[11,31,12]，需要插入的元素為12，但是12當前并沒有處于正確的位置，于是我們需要依次與前面的元素31、11做比較，一邊比較一邊移動比較過的元素，直到找到第一個比12小的元素11時停止比較，此時31對應的索引1則是12需要插入的位置。
3、Java排序算法之冒泡排序
冒泡排序可以算是最經(jīng)典的排序算法了，記得小弟上學時最先接觸的也就是這個算法了，因為實現(xiàn)方法最簡單，兩層for循環(huán)，里層循環(huán)中判斷相鄰兩個元素是否逆序，是的話將兩個元素交換，外層循環(huán)一次，就能將數(shù)組中剩下的元素中最小的元素"浮"到最前面，所以稱之為冒泡排序。
其實冒泡排序跟選擇排序比較相像，比較次數(shù)一樣，都為nx(n+1)/2，但是冒泡排序在挑選最小值的過程中會進行額外的交換(冒泡排序在排序中只要發(fā)現(xiàn)相鄰元素的順序不對就會進行交換，與之對應的是選擇排序，只會在內(nèi)層循環(huán)比較結束之后根據(jù)情況決定是否進行交換)，所以在我看來，選擇排序?qū)儆诿芭菖判虻母倪M版。
4、Java排序算法之希爾排序
希爾排序的誕生是由于插入排序在處理大規(guī)模數(shù)組的時候會遇到需要移動太多元素的問題。希爾排序的思想是將一個大的數(shù)組"分而治之",劃分為若干個小的數(shù)組，以gap來劃分，比如數(shù)組[1,2,3,4,5,6,7,8]，如果以gap=2來劃分，可以分為[1,3,5,7]和[2,4,6,8]兩個數(shù)組(對應的`，如gap=3，則劃分的數(shù)組為：[1,4,7]、[2,5,8]、[3,6])然后分別對劃分出來的數(shù)組進行插入排序，待各個子數(shù)組排序完畢之后再減小gap值重復進行之前的步驟，直至gap=1，即對整個數(shù)組進行插入排序，此時的數(shù)組已經(jīng)基本上快排好序了，所以需要移動的元素會很小很小，解決了插入排序在處理大規(guī)模數(shù)組時較多移動次數(shù)的問題。
具體實例請參照插入排序。
希爾排序是插入排序的改進版，在數(shù)據(jù)量大的時候?qū)π实奶嵘龓椭艽�，�?shù)據(jù)量小的時候建議直接使用插入排序就好了。
5、Java排序算法之歸并排序
歸并排序采用的是遞歸來實現(xiàn)，屬于"分而治之",將目標數(shù)組從中間一分為二，之后分別對這兩個數(shù)組進行排序，排序完畢之后再將排好序的兩個數(shù)組"歸并"到一起，歸并排序最重要的也就是這個"歸并"的過程，歸并的過程中需要額外的跟需要歸并的兩個數(shù)組長度一致的空間，比如需要規(guī)定的數(shù)組分別為：[3,6,8,11]和[1,3,12,15](雖然邏輯上被劃為為兩個數(shù)組，但實際上這些元素還是位于原來數(shù)組中的，只是通過一些index將其劃分成兩個數(shù)組，原數(shù)組為[3,6,8,11,1,3,12,15，我們設置三個指針lo,mid,high分別為0,3,7就可以實現(xiàn)邏輯上的子數(shù)組劃分)那么需要的額外數(shù)組的長度為4+4=8.歸并的過程可以簡要地概括為如下：
1)將兩個子數(shù)組中的元素復制到新數(shù)組copiedArray中，以前面提到的例子為例，則copiedArray=[3,6,8,11,1,3,12,15];
2)設置兩個指針分別指向原子數(shù)組中對應的第一個元素，假定這兩個指針取名為leftIdx和rightIdx，則leftIdx=0(對應copiedArray中的第一個元素[3])，rightIdx=4(對應copiedArray中的第五個元素[1]);
3)比較leftIdx和rightIdx指向的數(shù)組元素值，選取其中較小的一個并將其值賦給原數(shù)組中對應的位置i，賦值完畢后分別對參與賦值的這兩個索引做自增1操作，如果leftIdx或rigthIdx值已經(jīng)達到對應數(shù)組的末尾，則余下只需要將剩下數(shù)組的元素按順序copy到余下的位置即可。
下面給個歸并的具體實例：
1.第一趟：
2.3.輔助數(shù)組[21，28,39|35,38](數(shù)組被拆分為左右兩個子數(shù)組，以|分隔開)
4.5.[21，，，，](第一次21與35比較，左邊子數(shù)組勝出，leftIdx=0，i=0)
6.7.第二趟：
8.9.輔助數(shù)組[21,28，39|35,38]
10.11.[21，28,，，](第二次28與35比較，左邊子數(shù)組勝出，leftIdx=1，i=1)
12.13.第三趟：[21,28,39|35，38]
14.15.[21，28，35,，](第三次39與35比較，右邊子數(shù)組勝出，rightIdx=0，i=2)
16.17.第四趟：[21,28,39|35,38]
18.19.[21，28，35，38,](第四次39與38比較，右邊子數(shù)組勝出，rightIdx=1，i=3)
20.21.第五趟：[21,28,39|35,38]
22.23.[21，28，35，38，39](第五次時右邊子數(shù)組已復制完，無需比較leftIdx=2，i=4)
以上便是一次歸并的過程，我們可以將整個需要排序的數(shù)組做有限次拆分(每次一分為二)直到分為長度為1的小數(shù)組為止，長度為1時數(shù)組已經(jīng)不用排序了。在這之后再逆序(由于采用遞歸)依次對這些數(shù)組進行歸并操作，直到最后一次歸并長度為n/2的子數(shù)組，歸并完成之后數(shù)組排序也完成。
歸并排序需要的額外空間是所有排序中最多的，每次歸并需要與參與歸并的兩個數(shù)組長度之和相同個元素(為了提供輔助數(shù)組)。則可以推斷歸并排序的空間復雜度為1+2+4+…+n=nx(n+2)/4(忽略了n的奇偶性的判斷)，時間復雜度比較難估，這里小弟也忘記是多少了(囧)。
Java的五大排序算法2
簡單選擇排序：
（選出最小值，放在第一位，然后第一位向后推移，如此循環(huán)）第一位與后面每一個逐個比較，每次都使最小的置頂，第一位向后推進（即剛選定的第一位是最小值，不再參與比較，比較次數(shù)減1）
復雜度：所需進行記錄移動的操作次數(shù)較少0--3(n-1)，無論記錄的初始排列如何，所需的關鍵字間的比較次數(shù)相同，均為n(n-1)/2，總的時間復雜度為O(n2)；
空間復雜度O(1)
算法改進：每次對比，都是為了將最小的值放到第一位，所以可以一比到底，找出最小值，直接放到第一位，省去無意義的調(diào)換移動操作。也可以換一個方向，最后一位與前面每一個比較，每次使最大值沉底，最后一位向前推進。
復制代碼代碼如下:
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），每次都會在剩下的元素集合中選擇出一個最值出來填充到當前位置。唯一的區(qū)別是，冒泡排序在每次發(fā)現(xiàn)比當前值小于（或大于）時，都會交換元素的位置，而簡單選擇排序是選擇剩余元素中的最值和當前位置交換數(shù)據(jù)。
比如對于元素集合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小，但是他們并沒有交換數(shù)據(jù)）。
以下是簡單選擇排序的一個Java實現(xiàn)版本：
復制代碼代碼如下:
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個數(shù)，然后再構造出相對較小的[n+1]/4個數(shù)，直到只有一個元素為止。構造成一個完全二叉樹。
排序的時候，那個元素就是最小的，取出該最小元素，將該元素替換為"最大值",再調(diào)整完全二叉樹。
下面是樹形選擇排序的一個Java實現(xiàn)版：
復制代碼代碼如下:
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）{//如果是右節(jié)點
tmp[（j-1）/2]=tmp[j]>tmp[j-1]?tmp[j-1]:tmp[j];
j=（j-1）/2;
}else{//如果是左節(jié)點
tmp[j/2]=tmp[j]>tmp[j+1]?tmp[j+1]:tmp[j];
j=j/2;
}
}
}
}
在構造完全二叉樹的時候?qū)個元素的集合，需要2xN-1個輔助空間。
復制代碼代碼如下:
while（j>0）{
if（j%2==0）{//如果是右節(jié)點
tmp[（j-1）/2]=tmp[j]>tmp[j-1]?tmp[j-1]:tmp[j];
j=（j-1）/2;
}else{//如果是左節(jié)點
tmp[j/2]=tmp[j]>tmp[j+1]?tmp[j+1]:tmp[j];
j=j/2;
}
}
則實現(xiàn)遞歸的構造新集合中的最小值。
【Java的五大排序算法】相關文章：
java的常見排序方法04-03
PHP快速排序算法解析03-30
PHP排序算法類講解03-18
教你JAVA語言快速排序的原理03-30
C語言中使用快速排序算法對元素排序的實例03-18
java通用組合算法如何實現(xiàn)03-28
C語言選擇排序算法及實例代碼11-25
C語言插入排序算法及實例代碼12-05
C語言實現(xiàn)歸并排序算法實例04-01