乍一看這個(gè)需求是完不成的盯孙，因?yàn)槊芭菖判蛩惴ɑ驹頉Q定了需要兩層循環(huán)結(jié)構(gòu)咧擂。
要完成一個(gè)“真正的冒泡排序”至少要做到：
- 比較相鄰的元素榛做。如果第一個(gè)比第二個(gè)大痊末，就交換他們兩個(gè)蚕苇。
- 對(duì)每一對(duì)相鄰元素做同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)凿叠。第一輪完成后涩笤，最后的元素應(yīng)該會(huì)是最大的數(shù)嚼吞。
- 針對(duì)除最后一個(gè)元素外的所有的元素重復(fù)以上的步驟，獲得第二大的數(shù)蹬碧。這里是第一層循環(huán)舱禽。
- 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較恩沽。這里是第二層循環(huán)誊稚。
- 特別的，當(dāng)一輪比較過(guò)程中沒(méi)有發(fā)生交換罗心，則說(shuō)明所有元素順序已經(jīng)正確里伯，直接結(jié)束比較。
那難道真的沒(méi)有辦法在不使用循環(huán)結(jié)構(gòu)的情況下實(shí)現(xiàn)滿足這五點(diǎn)的排序算法嗎渤闷？
其實(shí)是可以做到的疾瓮，有一種手段可以實(shí)現(xiàn)類似于循環(huán)的功能，那就是遞歸飒箭。
想想求n的階乘的方法爷贫，除了寫一個(gè)循環(huán)體從1乘到n，還可以定義遞歸函數(shù)f(1)=1, f(x)=x*f(x-1)补憾。這樣就在不用循環(huán)的情況下完成了循環(huán)的功能。
那么要怎樣通過(guò)遞歸實(shí)現(xiàn)滿足上面5個(gè)要求的排序算法呢卷员？首先想想這個(gè)函數(shù)應(yīng)該有幾個(gè)變量盈匾。
數(shù)組肯定要，當(dāng)然靠定義全局變量也可以毕骡。
當(dāng)前位置肯定要削饵，因?yàn)楸容^的是相鄰元素，所以一個(gè)就夠未巫。
需要一個(gè)變量反應(yīng)循環(huán)輪次窿撬，如果一輪沒(méi)結(jié)束，應(yīng)該繼續(xù)比較下兩個(gè)元素叙凡；而一輪結(jié)束了則要開(kāi)始新一輪劈伴。這個(gè)變量可以是當(dāng)前這輪需要執(zhí)行比較的最后一個(gè)元素的位置。
還需要一個(gè)標(biāo)志位來(lái)判斷這一輪冒泡過(guò)程中是否發(fā)生了交換握爷，如果沒(méi)有那在一輪結(jié)束的時(shí)候就應(yīng)該結(jié)束排序跛璧。
一種可行的實(shí)現(xiàn)結(jié)果如下所示。需要注意第一次調(diào)用的時(shí)候結(jié)束位置是倒數(shù)第二個(gè)元素新啼，因而是a.lenth-2追城。
public class BubbleSort {
private static void bubbleSortWithoutLoop(int[] a, int pos, int endPos, boolean noChange){
// compare & bobble
if(a[pos]>a[pos+1]){
int temp = a[pos];
a[pos] = a[pos+1];
a[pos+1] = temp;
noChange = false;
}
// is the end of this round?
if(pos<endPos){
// continue this round
bubbleSortWithoutLoop(a,pos+1,endPos,noChange);
} else {
// if there has next round and need to go next round
if(endPos>0 && !noChange){
// next round
bubbleSortWithoutLoop(a,0,endPos-1,true);
}
// otherwise end the sort
}
}
public static void main(String[] args){
int[] a = {4,10,8,2,1,11,9,5,6,3,7};
bubbleSortWithoutLoop(a,0,a.length-2,true);
System.out.println(Arrays.toString(a));
}
}
輸出結(jié)果：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Process finished with exit code 0
