對算法中快速排序的總結

作為一個菜鳥，我用java寫了一篇沒有任何高深文法，僅僅用了遞歸的快速排序，可能有部分備援，歡迎大家斧正：

public static void quick(int[] array,int left,int right){
		int l=left+1;
		int r=right;
		int save=0;
		while(l<r){
			while(l<r&&array[left]>=array[l]){//這裡l<r不加等号，如果加了可能會突破右界限
				l++;
			}
			while(l<=r&&array[left]<array[r]){//重點：這裡要加等号，因為可能r會指向left，可以想想3,9,5怎麼排
				r--;
			}
			if(l>=r){
				break;
			}
			save=array[l];
			array[l]=array[r];
			array[r]=save;
		}
//		if(l==r){   這四行是錯誤代碼，可以試想一下9,3的排序。
//			l++;
//			r--;
//		}
		if(array[left]>array[r]){//這裡不能缺少判斷條件，否則可能會換錯。
			save=array[left];
			array[left]=array[r];
			array[r]=save;
		}
		if(left<r-1){
			quick(array, left, r-1);
		}
		if(r+1<right){
			quick(array, r+1, right);
		}
	}
           

這個算法也是我反複嘗試了很多次才成功的，重點主要有以下幾點：

1.while(l<r&&array[left]>=array[l]){//這裡l<r不加等号，如果加了可能會突破右界限

l++;

}

while(l<=r&&array[left]<array[r]){//重點：這裡要加等号，因為可能r會指向left，可以想想3,9,5怎麼排

r–;

}

這段代碼的第二行，等号是不能省的，如3,9,5；左指針在9，右指針在5，while循環過後，左指針在9，右指針在3，下次循環9和5會再排序（在if(r+1<right)中）。如果沒等号，那都指向9，下次就不會再排序了（因為r+1=right，r-1=left）。

2.

.if(l==r){ 這四行是錯誤代碼，可以試想一下9,3的排序。

l++;

r–;

}

這四行代碼是注釋，也是我之前出錯的原因之一，其實我之前是用中間值作為基準的，習慣性寫上這四行，其實随便想個例子就能把這幾行去掉。

3.

if(array[left]>array[r]){//這裡不能缺少判斷條件，否則可能會換錯。

save=array[left];

array[left]=array[r];

array[r]=save;

}

這裡可以想象3,9，本來排的是對的，但是左指針和右指針都指向9，不加判斷這兩個是會互換滴。

其實算法的架構和基本思路是最難想的，這些也不是一朝一夕能練成的，但是如何用代碼實作一個思路是可以訓練的，這就要不斷想象一個個例子，用例子去實驗直到代碼完全正确。